Optimization, approximation, and complexity classes

From MaRDI portal

Publication:1186548

Jump to:navigation, search

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)

zbMATH Keywords

optimization; approximability; MAX NP; MAX SNP

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Partition into cliques for cubic graphs: Planar case, complexity and approximation, The 0-1 inverse maximum stable set problem, The minimum substring cover problem, Maximizing business value by optimal assignment of jobs to resources in grid computing, Commitment under uncertainty: Two-stage stochastic matching problems, An improved lower bound on approximation algorithms for the closest substring problem, The transitive minimum Manhattan subnetwork problem in 3 dimensions, An updated survey on the linear ordering problem for weighted or unweighted tournaments, A mixed integer linear programming formulation of the maximum betweenness problem, Approximability of partitioning graphs with supply and demand, Parameterizing above or below guaranteed values, Routing to reduce the cost of wavelength conversion, Finding occurrences of protein complexes in protein-protein interaction graphs, Red-blue covering problems and the consecutive ones property, Connected domination of regular graphs, Vertex and edge covers with clustering properties: Complexity and algorithms, Paintshop, odd cycles and necklace splitting, Hardness results and approximation algorithms for (weighted) paired-domination in graphs, Cryptography with constant input locality, PTAS for connected vertex cover in unit disk graphs, Covering the edges of bipartite graphs using \(K_{2,2}\) graphs, Priority algorithms for graph optimization problems, Non-approximability of weighted multiple sequence alignment for arbitrary metrics, The labeled perfect matching in bipartite graphs, Efficient delay routing, A unified approximation algorithm for node-deletion problems, On a scheduling problem of time deteriorating jobs, Alphabet indexing for approximating features of symbols, On the approximation of protein threading, On the hardness of allocating frequencies for hybrid networks, A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses, Integer programming as a framework for optimization and approximability, Class Steiner trees and VLSI-design, Computational experience with approximation algorithms for the set covering problem, On the approximability of the Steiner tree problem in phylogeny, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, The computational complexity of some problems of linear algebra, Some MAX SNP-hard results concerning unordered labeled trees, Maximum bounded \(H\)-matching is Max SNP-complete, Oracle computations in parallel numerical linear algebra, The hardness of approximation: Gap location, Approximations for the maximum acyclic subgraph problem, A short note on the approximability of the maximum leaves spanning tree problem, On the power of multi-prover interactive protocols, Probabilistically checkable proofs and their consequences for approximation algorithms, Approximability of maximum splitting of k-sets and some other Apx-complete problems, On approximation algorithms for the minimum satisfiability problem, On an approximation measure founded on the links between optimization and polynomial approximation theory, New local search approximation techniques for maximum generalized satisfiability problems, Inferring a tree from walks, The hardness of approximate optima in lattices, codes, and systems of linear equations, On fixed-parameter tractability and approximability of NP optimization problems, The complexity and approximability of finding maximum feasible subsystems of linear relations, MNP: A class of NP optimization problems, Rounding algorithms for covering problems, Metafinite model theory, On the approximability of some Maximum Spanning Tree Problems, Non-approximability of weighted multiple sequence alignment., The task allocation problem with constant communication., Local approximations for maximum partial subgraph problem., On approximability of linear ordering and related NP-optimization problems on graphs., Hardness of approximation for non-overlapping local alignments., Distinguishing string selection problems., Differential approximation results for the Steiner tree problem, Some APX-completeness results for cubic graphs, Counting problems over the reals, Interactive and probabilistic proof-checking, Approximating minimum feedback vertex sets in hypergraphs, Clique is hard to approximate within \(n^{1-\epsilon}\), Structural properties of bounded relations with an application to NP optimization problems, A 2-approximation algorithm for the minimum weight edge dominating set problem, Hardness results for neural network approximation problems, Which problems have strongly exponential complexity?, A randomized approximation scheme for metric MAX-CUT, Computing similarity between RNA structures, On bounded occurrence constraint satisfaction, The complexity of minimizing and learning OBDDs and FBDDs, On the complexity of computing MP distance between binary phylogenetic trees, Sparsification and subexponential approximation, The many facets of upper domination, The complexity of secure domination problem in graphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Complexity of distance paired-domination problem in graphs, The approximability of non-Boolean satisfiability problems and restricted integer programming, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Order consolidation for batch processing, On the approximability of the maximum induced matching problem, Conversion of coloring algorithms into maximum weight independent set algorithms, On the complexity of finding emerging patterns, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Local search for the minimum label spanning tree problem with bounded color classes., On the complexity of the approximation of nonplanarity parameters for cubic graphs, Derandomized graph products, On the terminal Steiner tree problem., On the Hamming distance of constraint satisfaction problems., On weighted vs unweighted versions of combinatorial optimization problems, The nonapproximability of OBDD minimization, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Differential approximation for optimal satisfiability and related problems, Approximability of scheduling problems with resource consuming jobs, Combinatorial PCPs with short proofs, On the ordered list subgraph embedding problems, 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, Tractability-preserving transformations of global cost functions, Complexity of approximating CSP with balance/hard constraints, Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem, A nonmonotone GRASP, Graph editing to a fixed target, The maximum flow problem with disjunctive constraints, Approximability of the vertex cover problem in power-law graphs, A note on anti-coordination and social interactions, Exact algorithms and APX-hardness results for geometric packing and covering problems, Revisiting the minimum breakpoint linearization problem, Complexity of majority monopoly and signed domination problems, Max-leaves spanning tree is APX-hard for cubic graphs, 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 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, 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 the clustered set covering problem, The interval constrained 3-coloring problem, Unrelated parallel machine scheduling -- perspectives and progress, Approximating Max NAE-\(k\)-SAT by anonymous local search, On robust clusters of minimum cardinality in networks, Optimization problems in multiple subtree graphs, Complexity issues in vertex-colored graph pattern matching, Approximation algorithms for grooming in optical network design, Inapproximability of maximal strip recovery, Complexity and approximation of the constrained forest problem, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Combined super-/substring and super-/subsequence problems, Lagrangean bounds for the optimum communication spanning tree problem, Separator-based data reduction for signed graph balancing, The Stackelberg minimum spanning tree game, Uniform unweighted set cover: the power of non-oblivious local search, Computing bond orders in molecule graphs, Derandomized parallel repetition via structured PCPs, A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach, 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, Complexities of efficient solutions of rectilinear polygon cover problems, 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, A note on the descriptive complexity of maximization problems, Structure of polynomial-time approximation, Pseudo-Boolean optimization, The full Steiner tree problem, Minimal multicut and maximal integer multiflow: a survey, On the hardness of finding near-optimal multicuts in directed acyclic graphs, Schedules for marketing products with negative externalities, There is no EPTAS for two-dimensional knapsack, Hard constraint satisfaction problems have hard gaps at location 1, 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, 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 network flow approach to the minimum common integer partition problem, 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, 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, Subjective-cost policy routing, The multi-multiway cut problem, Parameterized and subexponential-time complexity of satisfiability problems and applications, On the complexity of the shortest-path broadcast problem, Complexity of total outer-connected domination problem in graphs, Methods for reconstructing the history of tandem repeats and their application to the human genome., Approximation algorithms for NMR spectral peak assignment., On the existence of subexponential parameterized algorithms, Approximation algorithm for MAX DICUT with given sizes of parts, Inapproximability results for equations over finite groups, Cluster graph modification problems, On decision and optimization (\(k\),\(l\))-graph sandwich problems, On the longest circuit in an alterable digraph, Normal forms for second-order logic over finite structures, and classification of NP optimization problems, Approximation algorithms for tree alignment with a given phylogeny, FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization, On the complexity of computing the temporal hybridization number for two phylogenies, Donation center location problem, Max NP-completeness made easy, Improved non-approximability results for minimum vertex cover with density constraints, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, On the maximum independent set problem in subclasses of subcubic graphs, Minimum vertex cover in ball graphs through local search, Hardness results, approximation and exact algorithms for liar's domination problem in graphs, An approximation of the minimum vertex cover in a graph, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks, Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation, The optimal statistical median of a convex set of arrays, The ferry cover problem, The complexity of finding harmless individuals in social networks, Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs, On subexponential and FPT-time inapproximability, The maximum clique problem in multiple interval graphs, Complexity of approximating bounded variants of optimization problems, Complexity and approximation of the minimum recombinant haplotype configuration problem, Logic minimization techniques with applications to cryptology, Fixed-parameter approximation: conceptual framework and approximability results, Approximability of identifying codes and locating-dominating codes, On constructing an optimal consensus clustering from multiple clusterings, Supermodular functions and the complexity of MAX CSP, Tai mapping hierarchy for rooted labeled trees through common subforest, On approximability of optimization problems related to red/blue-split graphs, The complexity of optimal design of temporally connected graphs, Large cuts with local algorithms on triangle-free graphs, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, On defensive alliances and strong global offensive alliances, Maximal strip recovery problem with gaps: hardness and approximation algorithms, Flip distance between triangulations of a planar point set is APX-hard, Computing the differential of a graph: hardness, approximability and exact algorithms, Network design with a discrete set of traffic matrices, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, Minimization of decision trees is hard to approximate, Inapproximability results for the lateral gene transfer problem, Linear time algorithms for generalized edge dominating set problems, A tutorial on the cross-entropy method, Reductions, completeness and the hardness of approximability, Independent set of intersection graphs of convex objects in 2D, A simple filter-and-fan approach to the facility location problem, Complexity results on restricted instances of a paint shop problem for words, A modified greedy algorithm for dispersively weighted 3-set cover, Minimum monopoly in regular and tree graphs, On the computational hardness based on linear fpt-reductions, On maximum planar induced subgraphs, A class of node based bottleneck improvement problems, Completeness in approximation classes beyond APX, Generalized \(k\)-multiway cut problems, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, A note on the complexity of minimum latency data aggregation scheduling with uniform power in physical interference model, Optimal deterministic auctions with correlated priors, The approximability of the weighted Hamiltonian path completion problem on a tree, Tight lower bounds for certain parameterized NP-hard problems, Parameterized computation and complexity: a new approach dealing with NP-hardness, A \(2^{|E|/4}\)-time algorithm for MAX-CUT, On approximate learning by multi-layered feedforward circuits, Complexity results for rainbow matchings, Approximating a class of combinatorial problems with rational objective function, Genus characterizes the complexity of certain graph problems: Some tight results, A survey on the linear ordering problem for weighted or unweighted tournaments, Polynomial approximation: a structural and operational study. (Abstract of thesis), Unnamed Item, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, On the Complexity Landscape of the Domination Chain, Upper Domination: Complexity and Approximation, Learning Hurdles for Sleeping Experts, On the Maximum Uniquely Restricted Matching for Bipartite Graphs, Moderately exponential time and fixed parameter approximation algorithms, Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap, Approximation of the Clustered Set Covering Problem, Safe Approximation and Its Relation to Kernelization, Grothendieck-Type Inequalities in Combinatorial Optimization, The Birth and Early Years of Parameterized Complexity, Parameterized Complexity and Subexponential-Time Computability, TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, Super-polynomial approximation branching algorithms, Approximability results for the converse connectedp-centre problem^†, On the complexity of variations of mixed domination on graphs^†, The Approximability of Partial Vertex Covers in Trees, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, How to Cut a Graph into Many Pieces, Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees, Restricted Common Superstring and Restricted Common Supersequence, Approximation Algorithms for Minimum Chain Vertex Deletion, Unnamed Item, Deterministic and randomized polynomial‐time approximation of radii, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD, Proving completeness by logic, Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa, On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Unnamed Item, On the Complexity of Finding a Potential Community, On Finding Small 2-Generating Sets, Grothendieck’s Theorem, past and present, On the Approximability of Comparing Genomes with Duplicates, On Maximum Edge Cuts of Connected Digraphs, The Minimum Substring Cover Problem, Order Scheduling Models: Hardness and Algorithms, Unnamed Item, A Logical Approach to Constraint Satisfaction, Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph, When polynomial approximation meets exact computation, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Repetition-free longest common subsequence, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Repetition-free longest common subsequence, The complexity of multiple sequence alignment with SP-score that is a metric, Maximizing agreements with one-sided error with applications to heuristic learning, Hardness and methods to solve CLIQUE, On the complexity of comparing evolutionary trees, Cardinality of relations and relational approximation algorithms, Maximizing agreements with one-sided error with applications to heuristic learning, On the complexity of the minimum outer-connected dominating set problem in graphs, Near optimal multiple alignment within a band in polynomial time, Approximation of a batch consolidation problem, Algorithmic Aspect of Minus Domination on Small-Degree Graphs, Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks, On Dinur’s proof of the PCP theorem, ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, Online Admission Control and Embedding of Service Chains, Approximating Alternative Solutions, Probabilistic CEGAR, Local Monotonicity in Probabilistic Networks, On the hardness of range assignment problems, atalog: A logic language for expressing search and optimization problems, Cost Minimisation in Multi-interface Networks, Maximum Motif Problem in Vertex-Colored Graphs, On Approximating an Implicit Cover Problem in Biology

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1186548&oldid=12051693"