排序方式: 共有56条查询结果,搜索用时 15 毫秒
1.
The complexity of searching minimum difference covers, both in Z+ and in Zn, is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Z+ and in Zn, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms. 相似文献
2.
Vojtech Blint 《Journal of Discrete Algorithms》2003,1(3-4):339-355
Let G be an undirected graph with two edge costs (c-cost and d-cost). We want to minimize the diameter of a spanning subgraph S (under d-cost) subject to the constraint that the total cost of the edges in S (with respect to c) does not exceed a given budget. We prove that this problem is non-approximable, even in some special cases. Similar results are proved if the stretch factor or the root stretch factor is considered instead of the diameter. 相似文献
3.
Analterable digraph is a digraph with a subset of its edges marked alterable and their orientations left undecided. We say that an alterable digraph has an invariant ofk on the length of the longest circuit if it has a circuit of length at leastk regardless of the orientations over its alterable edges. Computing the maximum invariant on the length of the longest circuit in an alterable digraph is aglobal optimization problem. We show that it is hard to approximate the global optimal solution for the maximum invariant problem.Research supported in part by NSF grant CCR 9121472. 相似文献
4.
《Operations Research Letters》2023,51(1):1-2
In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results. 相似文献
5.
《Operations Research Letters》2023,51(2):187-189
We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard. 相似文献
6.
Split cuts are prominent general-purpose cutting planes in integer programming. The split closure of a rational polyhedron is what is obtained after intersecting the half-spaces defined by all the split cuts for the polyhedron. In this paper, we prove that deciding whether the split closure of a rational polytope is empty is NP-hard, even when the polytope is contained in the unit hypercube. As a direct corollary, we prove that optimization and separation over the split closure of a rational polytope in the unit hypercube are NP-hard, extending an earlier result of Caprara and Letchford. 相似文献
8.
Let A be a 0 − 1 matrix with precisely two 1’s in each column and let 1 be the all-one vector. We show that the problems of deciding whether the linear system
(1) defines an integral polyhedron,
(2) is totally dual integral (TDI), and
(3) box-totally dual integral (box-TDI)
are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles
in 1984.
Supported in part by NSA grant H98230-05-1-0081 and NSF grants DMS-0556091 and ITR-0326387.
Supported in part by the Research Grants Council of Hong Kong and Seed Funding for Basic Research of HKU. 相似文献
9.
We provide a complexity analysis of the problem of optimal routing of a server on a transportation network in the presence of a competing server. The server that reaches a node first gets the profit from the node. The objective is to maximize the worst-case profit. 相似文献
10.
In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed. 相似文献