首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   19篇
  完全免费   2篇
  自动化技术   21篇
  2014年   1篇
  2011年   3篇
  2010年   2篇
  2009年   3篇
  2008年   3篇
  2007年   2篇
  2006年   2篇
  2005年   1篇
  2004年   2篇
  2003年   1篇
  2001年   1篇
排序方式: 共有21条查询结果,搜索用时 125 毫秒
1.
We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion times, including minimizing the lp norm of the vector of completion times. This generalizes and simplifies many previous results in this area.  相似文献
2.
This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.  相似文献
3.
We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.  相似文献
4.
货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.  相似文献
5.
We determine the computational complexity of the problem of ordering a set of n numbers, either into a sequence or a cycle, such that the maximum sum of any k successive numbers is minimal. Both problems are easy for k=2 and strongly NP-hard for any k?3. However, the two problems allow a polynomial-time approximation scheme that is linear in n.  相似文献
6.
This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.  相似文献
7.
M. Karpinski 《Algorithmica》2001,30(3):386-397
We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard combinatorial optimization problems. We indicate some inherent limits for the existence of such schemes for some other dense instances of optimization problems. We also go beyond the dense optimization problems and show how other approximation problems can be solved by using dense techniques. Received October 30, 1997; revised June 25, 1999, and April 17, 2000.  相似文献
8.
李曙光  李国君  王秀红 《软件学报》2006,17(10):2063-2068
考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工Bn个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).  相似文献
9.
二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε〉1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku^*/ku,kl^*/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。  相似文献
10.
We observe that the recent quasi-polynomial time approximation scheme (QPTAS) of Adamaszek and Wiese for the Maximum Weight Independent Set of Polygons problem, where polygons have at most a polylogarithmic number of vertices and nonnegative weights, yields:
1.
a QPTAS for the problem of finding, for a set S of n points in the plane, a planar straight-line graph (PSLG) whose vertices are the points in S and whose each interior face is a simple polygon with at most a polylogarithmic in n number of vertices such that the total weight of the inner faces is maximized, and in particular,  相似文献
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号