排序方式: 共有10条查询结果,搜索用时 312 毫秒
1
1.
研究了环型二元序列的赋权对换排序问题。定义一个长度为l的对换的费用是f(l)=lα,0≤α<1,对环型二元序列的赋权对换排序问题给出了一个O(logn)近似算法,其中n是环型二元序列的长度。 相似文献
2.
呼叫接纳控制是通讯网络设计与运营中的一个重要优化问题. 环网络中,这一问题的目标是对于给定的具有边容量的环网络和任意利润的呼叫的集合,确定最大利润的呼叫子集并为其中每一个呼叫安排路径,使得任一边容量不被违反. 对于无向和有向环网络呼叫接纳控制问题, 均给出了多项式时间近似方案. 相似文献
3.
4.
提出了对换排序的赋权模型,定义一个长度为l的对换的费用是f(l)=lα,α>0;分别给出了当0<α<1和1<α<2时,二元序列赋权对换排序问题的近似算法;证明了当α≥2时,起泡排序算法是此问题的精确算法. 相似文献
5.
考虑客户请求在圈中实现的问题. 每个请求联系着一个t 区间, 由圈上至多t(t1)个区间构成. 要实现一个请求, 需选择它所对应的t 区间中的一个区间并为其安排k种颜色中的一种. 任意两个选定的区间如果在圈上有公共边, 则不能得到同一种颜色. 对目标寻求实现最大数目的请求问题, 给出了一个3.042 近似算法. 相似文献
6.
考虑波分复用星形单跳网中的数据包传输调度问题, 假定诸发送机频率可调, 而接收机频率固定. 当m≥2时, 这一调度问题是NP-完备的, m表示所拥有的信道数目. 对目前所知最好的一个2-近似算法进行了精细的分析, 证明了m=3时, 该算法近似比为7/4, 并通过实例说明此结果为最佳可能. 相似文献
7.
考虑的基因组的进化基于两种形式:基因组中染色体之间的移位(translocation)和染色体内部的翻转(reversal).研究了标号基因组间的重组问题:求一个标号基因组进化成另一个标号基因组所需最少数目的移位和翻转,这个数目叫做重组距离.给出了求“共尾”标号基因组间重组距离的一个线性时间算法,从而改进了Hannenhalli和Pevzner的O(n^2)算法,其中n是基因组中基因的个数. 相似文献
8.
本文考虑极小化最大完工时间的单机分批加工问题.设有n个工件和一台批加工机器.每个工件有一个释放时间和一个加工时间.批加工机器可以同时加工b(b相似文献
9.
讨论均匀多部竞赛图,证明一个2-强连通2-均匀的n-部竞赛图(n≥6)包含一对分量共轭圈. 相似文献
10.
研究有组安装任务的单机窗时排序问题,所有工件的提前/延误惩罚费用相同;公共交货期窗口大小给定但位置待定,由线性定位费用衡量;最优排序是使所有这些费用的和最小.给出了最优排序的一些性质,提出一个多项式时间算法. 相似文献
1