【摘 要】
：
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exch
【机 构】
：
School of Information Science and Engineering,Central South University,Changsha 410083,China;Departm
【出 处】
：
2015全国理论计算机科学学术年会
论文部分内容阅读
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed graph.In generally, the objective function is maximizing the number of possible kidney transplants.In this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle exchanges.First, we formal the kidney exchange problem as a parameterized model.And then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the vertices.Last, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney problem.Moreover,our randomized algorithms can be extended to solve the general kidney exchange problem.
其他文献
本文利用太阳能毛细管网系统辅助火炕供暖,通过实验研究其对炕面温度和室内温度的影响,测试得出普通房间炕头、炕中、炕尾的平均温度分别为65.7℃、43.28℃、39.82℃,炕面温差大于20℃,而采用该系统的房间炕头、炕中、炕尾的平均温度分别为51.34℃、38.26℃、33.79℃,温度分布比普通火炕均匀,提高了炕面的舒适性;太阳能辅热火炕房间室内平均温度为18.5℃,比普通房间室内平均温度高6.3
本文通过实验测试研究毛细管网型太阳能供暖系统对室内舒适性的影响,得到结论为实验房间室内平均温度为16.66℃,而普通房间室内平均温度为10.2℃,温度提高6.46℃,并且白天太阳能房间的室内温度始终高于普通房间的室内温度,夜间停止运行时也能维持与普通房间基本一致的室内温度,可以有效提高农居室内热舒适性,实现对太阳能的极限利用,减少常规能源的消耗.毛细管网热惯性小,系统运行时室内温度升高较快,可依据
以兰纳素染料三原色对羊毛散纤维进行染色,通过改变工艺条件,对比染色后织物的各项性能,探索了最适合羊毛染色的工艺条件和参数.兰纳素染料染液pH应控制在4～5;在85℃、98℃、100℃下都可以进行染色;可适当加入元明粉,但用量应控制在5％(owf)以下;加入1％～2％的Albegal B可以同时起到提高上染速率和匀染的作用;中性条件下固色即可.以溴代丙烯酰胺为活性基的兰纳素染料三原色拥有较好的配伍性
对不同细度的莱卡包芯纱、涤纶包芯纱,在小样织机上采用三种不同纬密进行无纬织造,纱线表面受到摩擦后,对纱线断裂强力、断裂伸长率、断裂强力下降率、断裂伸长率下降率以及纱线外观形态进行测试分新.实验结果得到,包芯纱断裂强力随纬纱密度增加而减小,纱线强力降低率逐渐增大;纱线断裂伸长率降低率随着纬密增加而增大.随着纬密增加,经过摩擦后,纱线的外包纤维变得松散,纱线紧密度降低,毛羽增加.对于相同线密度的包芯纱
研究了以16tex、涤纶、凯斯林、粘胶、毛这四种纤维混纺纱,混纺比60/10/15/15/为代表产品的差别化涤粘毛多组份混纺纱线的生产工艺流程、工艺参数,原料选配;通过功能性阳离子改性涤纶、凯斯林、粘胶这三种纤维在清花工序预先进行混合成卷,用特殊的装置将特殊定制的精梳毛条在梳棉机后与之同时喂入混合,经并条、粗纱、细纱纺成纱线.通过小试、中试、批量生产过程中,对纤维内在指标的优选、对各道生产工序工艺
为了探索青椒适宜的贮藏温度,以园丰4号青椒为试材,从青椒贮藏期果实的呼吸强度、含水率、可溶性固形物、总糖、可滴定酸及Vc等各项生理生化指标着手,研究了六个不同贮藏温度(1℃、5℃、7℃、10℃、13℃)对青椒贮藏期品质的影响.结果表明,(1)青椒的冰点温度在-2℃～-3℃之间;(2)1℃贮藏的青椒易产生冷害现象;(3)5℃贮藏温度可降低青椒的呼吸强度,抑制青椒失水萎蔫、腐烂,并可减缓青椒果实整个贮
为建立鲜切蔬菜的货架期预测模型,在冰温储藏下,通过正交设计确定了菠菜鲜切处理的最佳方案为用75mg/LCLO2水溶液、0.5％NaCl溶液分别浸泡10min后,PVDC保鲜膜包装.通过对鲜切菠菜相关理化指标、菌落总数的测定及感官评价,跟踪样品品质随时间、温度的变化关系.结果表明,菠菜叶绿素含量随着贮藏时间的延长分别呈现出逐渐升高和降低的趋势.随着贮藏温度的升高,菠菜相关的各品质指标变化率也增大,且
为了探明猴头菇褐变机制并抑制褐变,研究了柠檬酸处理和贮藏温度对猴头菇褐变度、总酚含量、多酚氧化酶(PPO)活性、过氧化物酶(POD)活性的影响.结果表明,猴头菇在(15±0.5)℃条件下贮藏褐变严重,而(1±0.5)℃下贮藏能有效抑制其褐变,柠檬酸处理后在(15±0.5)℃条件下贮藏依然褐变严重.总酚含量和PPO活性、POD活性与猴头菇褐变相关,但不是褐变的诱发原因.
In this paper, we restudy busy beaver problem that is defined by Tibor Rado in 1962.Based on his work, we describe four decision problems-busy beaver problerr, max shifter problem, halting empty tape
In this paper, a novel approach for initializing clustering centers of K-Means algorithm is presented.This method is based on the variance of dimension, which is used as keyword to make a full permuta