The complexity of optimization problems

DOI10.1016/0022-0000(88)90039-6zbMath0652.68040OpenAlexW2072181151MaRDI QIDQ1107309

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6559

zbMATH Keywords

Coloring Bin packing Clique Knapsack NP-complete optimization problems Traveling salesperson

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Complexity results for some eigenvector problems, UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, The operators min and max on the polynomial hierarchy, Resource-bounded kolmogorov complexity revisited, The complexity class θp2: Recent results and applications in AI and modal logic, Unnamed Item, Generalized theorems on relationships among reducibility notions to certain complexity classes, On computing Boolean connectives of characteristic functions, On the approximability of the maximum common subgraph problem, Tailoring recursion for complexity, Structural analysis of the complexity of inverse functions, Structure in approximation classes, Mixed Iterated Revisions: Rationale, Algorithms, and Complexity, The Complexity of Aggregates over Extractions by Regular Expressions, Taking into account ``who said what in abstract argumentation: complexity results, Unnamed Item, Optimal length cutting plane refutations of integer programs, Dynamical Systems Theory and Algorithms for NP-hard Problems, The 1-Versus-2 Queries Problem Revisited, The Complexity Landscape of Outcome Determination in Judgment Aggregation, Polynomially bounded minimization problems which are hard to approximate, ANALYSIS OF QUANTUM FUNCTIONS, Reasoning with Uncertain and Inconsistent OWL Ontologies, Unnamed Item, The communication complexity of enumeration, elimination, and selection, Pure Nash equilibria in a generalization of congestion games allowing resource failures, Unnamed Item, Unnamed Item, SELF-SPECIFYING MACHINES, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, On the Complexity of Inverse Mixed Integer Linear Optimization, A taxonomy of complexity classes of functions, The complexity of optimizing finite-state transducers, Simple characterizations of \(P(\# P)\) and complete problems, A complexity theory for feasible closure properties, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Efficient timed model checking for discrete-time systems, Complexity of counting the optimal solutions, Nondeterministic functions and the existence of optimal proof systems, Computing Maximal Autarkies with Few and Simple Oracle Queries, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, Polynomial terse sets, Reductions between disjoint NP-pairs, Weighted Boolean Formula Games, The complexity of optimization problems, Unnamed Item, From causes for database queries to repairs and model-based diagnosis and back, A survey of one-way functions in complexity theory, Nondeterministic bounded query reducibilities, A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, Minimal sets on propositional formulae. Problems and reductions, Universally serializable computation, On the power of unambiguity in log-space, Pure Nash equilibria in a generalization of congestion games allowing resource failures, On the Complexity of Master Problems, The complexity of comparing optimal solutions, Updating action domain descriptions, Ancestors, descendants, and gardens of Eden in reaction systems, Complexity of Counting the Optimal Solutions, Timed negotiations, Most probable explanations in Bayesian networks: complexity and tractability, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], Complexity of manipulative interference in participatory budgeting, Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results, Non-uniform reductions, Counting Complexity of Minimal Cardinality and Minimal Weight Abduction, Bi-immunity results for cheatable sets, Two queries, The consequences of eliminating NP solutions, A survey on the structure of approximation classes, Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP, Optimal satisfiability for propositional calculi and constraint satisfaction problems., Some connections between bounded query classes and non-uniform complexity., Consistency checking and querying in probabilistic databases under integrity constraints, \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems, Bounded queries to SAT and the Boolean hierarchy, The Power of Self-Reducibility: Selectivity, Information, and Approximation, Two hardness results for Gamson's game, Constructive complexity, Optimization, approximation, and complexity classes, Frequency computation and bounded queries, Approximate solution of NP optimization problems, On quasilinear-time complexity theory, Computing functions with parallel queries to NP, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Generalizations of Opt P to the polynomial hierarchy, Traveling salesman problem and local search, Removing redundancy from a clause, Computing homotopic line simplification, Proving SAT does not have small circuits with an application to the two queries problem, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Deciding uniqueness in norm maximazation, Improving known solutions is hard, A very hard log-space counting class, Quantifiers and approximation, The 1-versus-2 queries problem revisited, On the autoreducibility of functions, The value of help bits in randomized and average-case complexity, A note on \(\#\mathcal P\)-completeness of NP-witnessing relations, Counting complexity of propositional abduction, Probabilistic spatio-temporal knowledge bases: capacity constraints, count queries, and consistency checking, Function operators spanning the arithmetical and the polynomial hierarchy, Preimage Problems for Reaction Systems, The complexity of power-index comparison, The complexity of error metrics, The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Heuristic NPN Classification for Large Functions Using AIGs and LEXSAT, Probabilistic polynomial time is closed under parity reductions, Monodirectional P systems, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Model Checking FO(R) over One-Counter Processes and beyond, Before and after vacuity, A nondeterministic Turing machine variant to compute functions, On the complexity of finding the chromatic number of a recursive graph. I: The bounded case, The complexity of belief update, Theory of one-tape linear-time Turing machines, Choice logics and their computational properties, Some structural properties of SAT, The variational quantum eigensolver: a review of methods and best practices, Default reasoning from conditional knowledge bases: Complexity and tractable cases, On the complexity of data disjunctions., Bounded queries, approximations, and the Boolean hierarchy, Optimal series-parallel trade-offs for reducing a function to its own graph, Kolmogorov characterizations of complexity classes, On the complexity of validity degrees in Łukasiewicz logic, Extending and implementing the stable model semantics, Completeness in approximation classes, The complexity of computing maximal word functions, On the query complexity of selecting minimal sets for monotone predicates, Some new results in the complexity of allocation and binding in data path synthesis

Cites Work