Optimization, approximation, and complexity classes
From MaRDI portal
Publication:1186548
DOI10.1016/0022-0000(91)90023-XzbMath0765.68036WikidataQ89894956 ScholiaQ89894956MaRDI QIDQ1186548
Christos H. Papadimitriou, Mihalis Yannakakis
Publication date: 28 June 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (only showing first 100 items - show all)
On the ordered list subgraph embedding problems ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Orienting graphs to optimize reachability ⋮ The NPO-completeness of the longest Hamiltonian cycle problem ⋮ Approximate Max \(k\)-Cut with subgraph guarantee ⋮ Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat} ⋮ A natural family of optimization problems with arbitrarily small approximation thresholds ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Tractability-preserving transformations of global cost functions ⋮ Complexity issues in color-preserving graph embeddings ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ On the longest common rigid subsequence problem ⋮ Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem ⋮ Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks ⋮ Strong computational lower bounds via parameterized complexity ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ Finding disjoint paths with related path costs ⋮ Analyzing the complexity of finding good neighborhood functions for local search algorithms ⋮ A nonmonotone GRASP ⋮ A network flow approach to the minimum common integer partition problem ⋮ Graph editing to a fixed target ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ The maximum flow problem with disjunctive constraints ⋮ Combined super-/substring and super-/subsequence problems ⋮ On the complexity of deriving position specific score matrices from positive and negative sequences ⋮ The longest common subsequence problem for arc-annotated sequences ⋮ Differential approximation of MIN SAT, MAX SAT and related problems ⋮ Power optimization for connectivity problems ⋮ Computing the minimum number of hybridization events for a consistent evolutionary history ⋮ Approximability of the vertex cover problem in power-law graphs ⋮ A note on anti-coordination and social interactions ⋮ Subjective-cost policy routing ⋮ The multi-multiway cut problem ⋮ Lagrangean bounds for the optimum communication spanning tree problem ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Revisiting the minimum breakpoint linearization problem ⋮ Separator-based data reduction for signed graph balancing ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Complexity of majority monopoly and signed domination problems ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ The Stackelberg minimum spanning tree game ⋮ 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 ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ Computing bond orders in molecule graphs ⋮ The locomotive fleet fueling problem ⋮ NP-completeness and APX-completeness of restrained domination in graphs ⋮ On the approximability of some degree-constrained subgraph problems ⋮ The traveling salesman problem with flexible coloring ⋮ Derandomized parallel repetition via structured PCPs ⋮ Online maximum directed cut ⋮ On scheduling \textsc{DAGs} for volatile computing platforms: area-maximizing schedules ⋮ Algorithmic aspects of \(k\)-tuple total domination in graphs ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ A survey on the structure of approximation classes ⋮ Reoptimization of max \(k\)-cover: approximation ratio threshold ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Approximation algorithms for intersection graphs ⋮ Independent dominating set problem revisited ⋮ The computational complexity and approximability of a series of geometric covering problems ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach ⋮ A note on the clustered set covering problem ⋮ Approximate solution of NP optimization problems ⋮ On input read-modes of alternating Turing machines ⋮ A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law ⋮ The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness ⋮ Local search, reducibility and approximability of NP-optimization problems ⋮ Alignment of trees -- an alternative to tree edit ⋮ The interval constrained 3-coloring problem ⋮ Complexities of efficient solutions of rectilinear polygon cover problems ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Approximating Max NAE-\(k\)-SAT by anonymous local search ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees ⋮ Randomized approximation of bounded multicovering problems ⋮ Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ On robust clusters of minimum cardinality in networks ⋮ A note on the descriptive complexity of maximization problems ⋮ Optimization problems in multiple subtree graphs ⋮ Structure of polynomial-time approximation ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Pseudo-Boolean optimization ⋮ The full Steiner tree problem ⋮ Approximation algorithms for grooming in optical network design ⋮ Inapproximability of maximal strip recovery ⋮ Complexity and approximation of the constrained forest problem ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Clustering with lower-bounded sizes. A general graph-theoretic framework ⋮ Schedules for marketing products with negative externalities ⋮ There is no EPTAS for two-dimensional knapsack ⋮ Approximability of scheduling problems with resource consuming jobs ⋮ Combinatorial PCPs with short proofs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of optimization problems
- Structure preserving reductions among convex optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
- How well can a graph be n-colored?
- Non deterministic polynomial optimization problems and their approximations
- On the complexity of approximating the independent set problem
- Approximation algorithms for combinatorial problems
- The Complexity of Near-Optimal Graph Coloring
- Some Examples of Difficult Traveling Salesman Problems
This page was built for publication: Optimization, approximation, and complexity classes
