This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by...
详细信息
This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The paper considers a number of classical scheduling objectives in this environment, under a variety of assumptions about setup and processing times. For each problem considered, the intention is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness;The results provide a mapping of the computational complexity of these problems. (C) 2000 Elsevier Science B.V. All rights reserved.
A dynamic network consists of a graph with capacities and transit times on its edges. The quickest transshipment problem is defined by a dynamic network with several sources and sinks, each source has a specified supp...
详细信息
A dynamic network consists of a graph with capacities and transit times on its edges. The quickest transshipment problem is defined by a dynamic network with several sources and sinks, each source has a specified supply and each sink has a specified demand. The problem is to send exactly the right amount of flow our of each source and into each sink in the minimum overall time. Variations of the quickest transshipment problem have been studied extensively: the special case of the problem with a single sink is commonly used to model building evacuation. Similar dynamic network Row problems have numerous other applications: in some of these, the capacities are small integers and it is important to rind integral Rows. There are no polynomial-time algorithms known for most of these problems. In this paper we give the first polynomial-time algorithm for the quickest transshipment problem. Our algorithm provides an integral optimum flow. Previously, the quickest transshipment problem could only be solved efficiently in the special case of a single source and single sink.
We consider a specific class of satisfiability (SAT) problems, the conjunctions of (nested) equivalencies (CoE). It is well known that CNF (conjunctive normal form) translations of CoE formulas are hard for branching ...
详细信息
We consider a specific class of satisfiability (SAT) problems, the conjunctions of (nested) equivalencies (CoE). It is well known that CNF (conjunctive normal form) translations of CoE formulas are hard for branching and resolution algorithms. Tseitin proved that regular resolution requires a running time exponential in the size of the input. We review a polynomialtimealgorithm for solving CoE formulas, and address the problem of recognizing a CoE formula by its CNF representation. Making use of elliptic approximations of 3SAT problems, the so-called doubly balanced 3SAT formulas can be seen to be equivalent to CoE formulas. Subsequently, the notion of doubly balancedness is generalized by using polynomial representations of satisfiability problems, to obtain a general characterization of CoE formulas. We briefly address the problem of finding CoE subformulas, and finally the application of the developed theory to several DIMACS benchmarks is discussed. (C) 2000 Elsevier Science B.V. All rights reserved.
The problem of recovering the structure of crystalline materials from their discrete X-rays is of fundamental interest in many practical applications. An important special case concerns determining the position of ato...
详细信息
The problem of recovering the structure of crystalline materials from their discrete X-rays is of fundamental interest in many practical applications. An important special case concerns determining the position of atoms of several different types in the integer lattice, given the number of each type lying on each line parallel to some lattice directions. We show that the corresponding consistency problem is NP-complete for any two (or more) different (fixed) directions when six (or more) types of atoms are involved. (C) 2000 Elsevier Science B.V. All rights reserved.
In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation, For a special subclass: of dir problems we show that the SDP relaxation provides an exact optimal ...
详细信息
In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation, For a special subclass: of dir problems we show that the SDP relaxation provides an exact optimal solution, Another subclass, which is NP-hard. guarantees that the SDP relaxation yields an approximate solution with a worst-case performance ratio of 0.87856.... This is a generalization of the well-known result uf Goemans and Williamson fur the maximum-cut problem. Finally, we discuss extensions of these results in the presence of a certain type of sign restrictions.
For a given graph G and p pairs (s(i), t(i)), 1 less than or equal to i less than or equal to p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P-i, 1 less than or equal to...
详细信息
For a given graph G and p pairs (s(i), t(i)), 1 less than or equal to i less than or equal to p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P-i, 1 less than or equal to i less than or equal to p, connecting s(i) and t(i). Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but the edge-disjoint paths problem is NP-complete even for partial 3-trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k-trees. The first one serves the problem for any partial k-tree G and runs in polynomialtime if p = O(log n) and in linear time if p = O(1), where n is the number of vertices in G. The second one solves the problem under some restriction on the location of terminal pairs even if p greater than or equal to log n.
We present a deterministic polynomial-time algorithm for the A B C problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial-tim...
详细信息
We present a deterministic polynomial-time algorithm for the A B C problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial-time algorithm for the (easier) membership problem for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions.
We consider a polynomial-time algorithm for the following scheduling problem: Given two machines, where each machine can process at most one job at a time;a set of jobs, where each job can start on or after its releas...
详细信息
We consider a polynomial-time algorithm for the following scheduling problem: Given two machines, where each machine can process at most one job at a time;a set of jobs, where each job can start on or after its release date and consists of a chain of unit-time operations such that the machines have to process them by turn begining with a given machine;find a schedule minimizing the maximum job completion time. Formerly, only pseudopolynomial-time algorithms have been proposed for this problem.
We study the computational complexity of various inverse problems in discrete tomography. These questions are motivated by demands from the material sciences for the reconstruction of crystalline structures from image...
详细信息
We study the computational complexity of various inverse problems in discrete tomography. These questions are motivated by demands from the material sciences for the reconstruction of crystalline structures from images produced by quantitative high resolution transmission electron microscopy. We completely settle the complexity status of the basic problems of existence (data consistency), uniqueness (determination), and reconstruction of finite subsets of the d-dimensional integer lattice Z(d) that are only accessible via their line sums (discrete X-rays) in some prescribed finite set of lattice directions. Roughly speaking, it turns out that for all d greater than or equal to 2 and for a prescribed but arbitrary set of m greater than or equal to 2 pairwise nonparallel lattice directions, the problems are solvable in polynomialtime if m=2 and are NP-complete (or NP-equivalent) otherwise. (C) 1999 Elsevier Science B.V. All rights reserved.
In this note we show that the stability number of a (4-pan, chair, K-1,K-4,P-5)-free graph which has no simplicial vertex is bounded by 3. This generalizes the case of (claw, P-5)-free graphs and leads to a very simpl...
详细信息
In this note we show that the stability number of a (4-pan, chair, K-1,K-4,P-5)-free graph which has no simplicial vertex is bounded by 3. This generalizes the case of (claw, P-5)-free graphs and leads to a very simple polynomial-time algorithm for determining the stability number of (claw, Ps)-free graphs and, more generally, of (4-pan,chair, K-1,K-4, P-5)-free graphs. (C) 1999 Elsevier Science B.V. All rights reserved.
暂无评论