Optimization, approximation, and complexity classes

DOI10.1016/0022-0000(91)90023-XzbMATH Open0765.68036WikidataQ89894956 ScholiaQ89894956MaRDI QIDQ1186548FDOQ1186548

Authors: Christos Papadimitriou, Mihalis Yannakakis

Publication date: 28 June 1992

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

Recommendations

scientific article; zbMATH DE number 847149
Approximate solution of NP optimization problems
Completeness in approximation classes
scientific article; zbMATH DE number 17535

optimization approximability MAX NP MAX SNP

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

Title not available (Why is that?)
Approximation algorithms for combinatorial problems
Title not available (Why is that?)
The complexity of optimization problems
Structure preserving reductions among convex optimization problems
Title not available (Why is that?)
Title not available (Why is that?)
On the complexity of approximating the independent set problem
Non deterministic polynomial optimization problems and their approximations
The Complexity of Near-Optimal Graph Coloring
Some Examples of Difficult Traveling Salesman Problems
Toward a unified approach for the classification of NP-complete optimization problems
How well can a graph be n-colored?

Cited In (only showing first 100 items - show all)

The approximability of the weighted Hamiltonian path completion problem on a tree
On Approximating an Implicit Cover Problem in Biology
Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
A note on the descriptive complexity of maximization problems
Algorithmic aspects of total Roman and total double Roman domination in graphs
APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
Interactive and probabilistic proof-checking
On the complexity of finding emerging patterns
On fixed-parameter tractability and approximability of NP optimization problems
Complexity issues in color-preserving graph embeddings
Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
On the longest common rigid subsequence problem
On approximate learning by multi-layered feedforward circuits
Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks
Analyzing the complexity of finding good neighborhood functions for local search algorithms
The complexity of secure domination problem in graphs
A network flow approach to the minimum common integer partition problem
On the hardness of finding near-optimal multicuts in directed acyclic graphs
Clustering with lower-bounded sizes. A general graph-theoretic framework
Algorithmic aspects of Roman domination in graphs
The complexity of finding harmless individuals in social networks
From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
A class of spectral bounds for max \(k\)-cut
On a scheduling problem of time deteriorating jobs
On the complexity of deriving position specific score matrices from positive and negative sequences
Cardinality of relations and relational approximation algorithms
A branch-and-bound algorithm for solving max-\(k\)-cut problem
Title not available (Why is that?)
Schedules for marketing products with negative externalities
Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
Approximation algorithms for NMR spectral peak assignment.
Minimization of decision trees is hard to approximate
The optimal statistical median of a convex set of arrays
On the complexity of the shortest-path broadcast problem
On bounded occurrence constraint satisfaction
Parameterized computation and complexity: a new approach dealing with NP-hardness
Parameterized and subexponential-time complexity of satisfiability problems and applications
Approximability of covering cells with line segments
Intractability of assembly sequencing: Unit disks in the plane
Integer programming as a framework for optimization and approximability
Polynomially bounded minimization problems which are hard to approximate
Upper Domination: Complexity and Approximation
Inapproximability results for the lateral gene transfer problem
Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
Title not available (Why is that?)
Approximability of identifying codes and locating-dominating codes
On the approximation of protein threading
A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
Flip distance between triangulations of a planar point set is APX-hard
A \(2^{|E|/4}\)-time algorithm for MAX-CUT
On input read-modes of alternating Turing machines
A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law
Complexity and approximability of quantified and stochastic constraint satisfaction problems
Approximation Classes for Real Number Optimization Problems
Polynomial time approximation algorithms for machine scheduling: Ten open problems
Revisiting the minimum breakpoint linearization problem
Order Scheduling Models: Hardness and Algorithms
Assortment planning for multiple chain stores
Practical algorithms for MSO model-checking on tree-decomposable graphs
On the power of multi-prover interactive protocols
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
The Maximum k-Colorable Subgraph Problem and Related Problems
Complexities of efficient solutions of rectilinear polygon cover problems
Reoptimization of max \(k\)-cover: approximation ratio threshold
Power optimization for connectivity problems
A Logical Approach to Constraint Satisfaction
On the terminal Steiner tree problem.
Optimization problems in multiple subtree graphs
Partition into cliques for cubic graphs: Planar case, complexity and approximation
Using fractional primal-dual to schedule split intervals with demands
Tight lower bounds for certain parameterized NP-hard problems
A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
On the approximability and hardness of minimum topic connected overlay and its special instances
The full Steiner tree problem
Paintshop, odd cycles and necklace splitting
Repetition-free longest common subsequence
On the approximability of the Steiner tree problem in phylogeny
On the complexity of computing the temporal hybridization number for two phylogenies
Exact algorithms and hardness results for geometric red-blue hitting set problem
Red-blue covering problems and the consecutive ones property
PTAS for connected vertex cover in unit disk graphs
A 2-approximation algorithm for the minimum weight edge dominating set problem
The locomotive fleet fueling problem
Minimum monopoly in regular and tree graphs
Rounding algorithms for covering problems
Restricted common superstring and restricted common supersequence
On the complexity of the multicut problem in bounded tree-width graphs and digraphs
On Maximum Edge Cuts of Connected Digraphs
NP-completeness and APX-completeness of restrained domination in graphs
The traveling salesman problem with flexible coloring
Linear time algorithms for generalized edge dominating set problems
Studying the complexity of global verification for NP-hard discrete optimization problems
On robust clusters of minimum cardinality in networks
Grothendieck-type inequalities in combinatorial optimization
Combined super-/substring and super-/subsequence problems
Inapproximability of maximal strip recovery
Complexity of most vital nodes for independent set in graphs related to tree structures
Inferring a tree from walks
On the computational hardness based on linear fpt-reductions

This page was built for publication: Optimization, approximation, and complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186548)