`` Strong NP-Completeness Results

DOI10.1145/322077.322090zbMath0379.68035OpenAlexW2009990213WikidataQ55899907 ScholiaQ55899907MaRDI QIDQ4158479

Michael R. Garey, David S. Johnson

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322077.322090

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Minimizing the weighted number of tardy jobs on multiple machines: a review, Feasibility of scheduling lot sizes of two frequencies on one machine, \(\kappa\)-partitioning problems for maximizing the minimum load, A NOTE ON COMPLEXITY OF GENETIC MUTATIONS, A dynamic tree algorithm for peer-to-peer ridesharing matching, Minimising total flow-time on two parallel machines with planned downtimes and resumable jobs, Using a tabu search approach for solving the two-dimensional irregular cutting problem, A convex geometric approach to counting the roots of a polynomial system, A graph partitioning heuristic for the parallel pseudo-exhaustive logical test of VLSI combinational circuits, A branch-and-price-and-cut approach for sustainable crop rotation planning, A survey on scheduling problems with due windows, A parallel machine schedule updating game with compensations and clients averse to uncertain loss, Scheduling shops to minimize the weighted number of late jobs, Tropically convex constraint satisfaction, On component-size bounded Steiner trees, A new algorithm for the propositional satisfiability problem, Polynomially solvable cases for the maximum stable set problem, Polynomial time approximation schemes for class-constrained packing problems, Shop scheduling problems with multiprocessor tasks on dedicated processors, Judicious partitions of hypergraphs, On locating cubic subgraphs in bounded-degree connected bipartite graphs, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Graphically structured value-function compilation, Tool-feeder partitions for module assignment in PCB assembly, A fast two-level variable neighborhood search for the clustered vehicle routing problem, Black and White Bin Packing Revisited, On the use of Boolean methods for the computation of the stability number, A local search approach for two-dimensional irregular cutting, Maximizing the weighted number of on-time jobs in single machine scheduling with time windows, Single machine scheduling with discretely controllable processing times, An optimal algorithm for preemptive on-line scheduling, Two-stage matching-and-scheduling algorithm for real-time private parking-sharing programs, On the two-connected planar spanning subgraph polytope, The algorithmic use of hypertree structure and maximum neighbourhood orderings, On maximum common subgraph problems in series-parallel graphs, A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times, Covering regular graphs, An improved algorithm for the \(L_2-L_p\) minimization problem, FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization, Is a unit-job shop not easier than identical parallel machines?, Priority-oriented route network planning for evacuation in constrained space scenarios, On scheduling with non-increasing time slot cost to minimize total weighted completion time, Complexity of unconstrained \(L_2 - L_p\) minimization, Betweenness parameterized above tight lower bound, Scheduling jobs with a V-shaped time-dependent processing time, On approximability of linear ordering and related NP-optimization problems on graphs., Approximation for knapsack problems with multiple constraints, Analysis of Smith's rule in stochastic machine scheduling, Path constraints in semistructured data, A Comparison of Random Task Graph Generation Methods for Scheduling Problems, The harmonious coloring problem is NP-complete for interval and permutation graphs, Deciding non-emptiness of hypergraph languages generated by connection-preserving fusion grammars is NP-complete, Best fit bin packing with random order revisited, Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs, The piggyback transportation problem: transporting drones launched from a flying warehouse, A metric approach for scheduling problems with minimizing the maximum penalty, Scheduling on uniform processors with at most one downtime on each machine, Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints, Operations research methods in preventing domino accidents in the chemical process industry (Abstract of thesis), Task assignment algorithms for two-type heterogeneous multiprocessors, An EPTAS for scheduling fork-join graphs with communication delay, Approximating a vehicle scheduling problem with time windows and handling times, Data dependent worst case bounds for weighted set packing, Controlling the losing probability in a monotone game, Multiprocessor scheduling under precedence constraints: polyhedral results, An approximation algorithm for maximum triangle packing, Worst-case analysis for on-line service policies, Scheduling reclaimer operations in the stockyard to minimize makespan, Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems, The edge-orientation problem and some of its variants on weighted graphs, Schaefer's Theorem for Graphs, Easy knapsacks and the complexity of energy allocation problems in the smart grid, Semidefinite and linear programming integrality gaps for scheduling identical machines, Optimally solving a versatile traveling salesman problem on tree networks with soft due dates and multiple congestion scenarios, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs, An approximation algorithm for computing longest paths., Makespan minimization with OR-precedence constraints, Fault tolerant \(K\)-center problems, The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability, On the NP-hardness of edge-deletion and -contraction problems, An effective quasi-human based heuristic for solving the rectangle packing problem, Single machine earliness-tardiness scheduling with resource-dependent release dates, Applying extra-resource analysis to load balancing., A note on minimum makespan assembly plans, Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs, On weighted vs unweighted versions of combinatorial optimization problems, Modeling uncertainty in networks, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Online Scheduling on Two Parallel Machines with Release Times and Delivery Times, Complexity and approximation of the smallest \(k\)-enclosing ball problem, A note on generalizing the maximum lateness criterion for scheduling, A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Compiling constraint satisfaction problems, Minimizing makespan on parallel machines subject to release dates and delivery times, Scheduling problems with a common due window assignment: A survey, Online scheduling on two parallel machines with release dates and delivery times, A note on the Coffman-Sethi bound for LPT scheduling, Database placement in communication networks for minimizing the overall transmission cost, Performance guarantees of local search for minsum scheduling problems, The complexity of the 0/1 multi-knapsack problem, An asymptotically exact polynomial algorithm for equipartition problems, Minimal triangulations of graphs: a survey, A compact labelling scheme for series-parallel graphs, Unimodular functions, The two-machine sequence dependent flowshop scheduling problem, Computation on binary tree-networks, The principle of optimality in the design of efficient algorithms, An approximation algorithm for maximum packing of 3-edge paths, A note on scheduling multiprocessor tasks with precedence constraints on parallel processors, Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem, Edge-connectivity augmentation problems, NP-completeness of the linear complementarity problem, A note on complete problems for complexity classes, Practical solutions for a dock assignment problem with trailer transportation, Approximation of the parallel machine scheduling problem with additional unit resources, Optimal broadcast domination in polynomial time, The maximum k-colorable subgraph problem for chordal graphs, Sink location to find optimal shelters in evacuation planning, Approximation schemes for Euclidean vehicle routing problems with time windows, The \(p\)-median problem: a survey of metaheuristic approaches, Single machine scheduling problems with resource dependent release times, Algorithms to solve the orienteering problem: A comparison, Deleting completed transactions, Tighter bounds of the First Fit algorithm for the bin-packing problem, `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders, Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center, Lot-sizing scheduling with batch setup times, On the Boolean connectivity problem for Horn relations, Multi-criteria scheduling: an agent-based approach for expert knowledge integration, Cop-robber guarding game with cycle robber-region, The node-deletion problem for hereditary properties is NP-complete, Complexity results for scheduling chains on a single machine, Toward a unified approach for the classification of NP-complete optimization problems, Approximation schemes for generalized two-dimensional vector packing with application to data placement, Online scheduling with rearrangement on two related machines, Parallel machines scheduling with machine maintenance for minsum criteria, Non deterministic polynomial optimization problems and their approximations, Scheduling jobs with equal processing times subject to machine eligibility constraints, Scheduling on same-speed processors with at most one downtime on each machine, On minimal augmentation of a graph to obtain an interval graph, A probabilistic analysis of the multiknapsack value function, General approximation algorithms for some arithmetical combinatorial problems, A note on the complexity of \(L _{p }\) minimization, Scheduling batches on parallel machines with major and minor set-ups, Online scheduling with one rearrangement at the end: revisited, Analysis of relaxations for the multi-item capacitated lot-sizing problem, Guard games on graphs: keep the intruder out!, Optimal algorithms for online scheduling with bounded rearrangement at the end, The complexity of equality constraint languages, Chordal graphs and upper irredundance, upper domination and independence, The hierarchical network design problem with transshipment facilities, Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems, COSINE: A new graph coloring algorithm, Finding large holes, Constructive complexity, A faster algorithm for the resource allocation problem with convex cost functions, Approximate solution of NP optimization problems, Knapsack problems for NL, Complexity of fixed-size bit-vector logics, Location and sizing of offshore platforms for oil exploration, Limitations of incremental dynamic programming, Scheduling multiprocessor tasks on three dedicated processors, A logic for programming with complex objects, An efficient algorithm for finding a maximum weight 2-independent set on interval graphs, On reversal-bounded picture languages, Maximizing business value by optimal assignment of jobs to resources in grid computing, Approximating the tree and tour covers of a graph, The max clique problem in classes of string-graphs, Structure of polynomial-time approximation, A linear kernel for a planar connected dominating set, Minimal split completions, Finding the longest isometric cycle in a graph, A minimum 3-connectivity augmentation of a graph, Theoretical investigations on maximal dual feasible functions, A greedy approximation for minimum connected dominating sets, On the complexity of decidable cases of the commutation problem of languages, Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint, On the complexity of crossings in permutations, Optimal and heuristic solution methods for a multiprocessor machine scheduling problem, Approximation algorithms for scheduling unrelated parallel machines, Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem, Computational complexity of norm-maximization, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm, A heuristic algorithm for the mini-max spanning forest problem, A branch-and-bound algorithm for the mini-max spanning forest problem, Bounding prefix transposition distance for strings and permutations, How hard is it to find extreme Nash equilibria in network congestion games?, PTAS for connected vertex cover in unit disk graphs, Minimum directed 1-subtree relaxation for score orienteering problem, The largest tree in a random graph, Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses, On legal path problems in digraphs, Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete, On the computational complexity of path cover problems, Fuzzy shortest paths, Planar graph coloring is not self-reducible, assuming P\(\neq NP\), Cellular automata and discrete neural networks, A bound for the Dilworth number, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation, Symmetry-driven network reconstruction through pseudobalanced coloring optimization, A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum, A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing, Scheduling with deterioration effects and maintenance activities under parallel processors, Worst-case analysis of LPT scheduling on a small number of non-identical processors, Exact and heuristic solution approaches for energy-efficient identical parallel machine scheduling with time-of-use costs, Computing welfare-maximizing fair allocations of indivisible goods, On the complexity of scheduling unrelated parallel machines with limited preemptions, Computational Complexity of Atomic Chemical Reaction Networks, Dominating cliques in graphs, A Tight (3/2+ε) Approximation for Skewed Strip Packing., A note on LPT scheduling, Scheduling with variable time slot costs, The computational complexity of the criticality problems in a network with interval activity times, Algorithms for minclique scheduling problems, On the complexity of coupled-task scheduling, LPT online strategy for parallel-machine scheduling with kind release times, The complexity of the network design problem, Realization problems on reachability sequences, NP-Complete operations research problems and approximation algorithms, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability, Best Fit Bin Packing with Random Order Revisited, On solving Travelling Salesman Problem with Vertex Requisitions, Parallel flowshop scheduling using Tabu search, Constraint Satisfaction Problems with Infinite Templates, Scheduling Opposing Forests, Unnamed Item