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)
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the complexity of the shortest-path broadcast problem, Complexity of total outer-connected domination problem in graphs, 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, Approximability and hardness of geometric hitting set with axis-parallel rectangles, Computational study of valid inequalities for the maximum \(k\)-cut problem, 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, Complexity and lowers bounds for power edge set problem, Restricted assignment scheduling with resource constraints, Affine reductions for LPs and SDPs, Limitations of semidefinite programs for separable states and entangled games, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Finding a potential community in networks, Finding a most parsimonious or likely tree in a network with respect to an alignment, Deciding the existence of a cherry-picking sequence is hard on two trees, Approximation algorithms for connected graph factors of minimum weight, Competitive algorithms for multistage online scheduling, On unrooted and root-uncertain variants of several well-known phylogenetic network problems, 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, 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, NP-completeness: A retrospective, A primal-dual approach to approximation of node-deletion problems for matroidal properties, The approximation of maximum subgraph problems, Polynomially bounded minimization problems which are hard to approximate, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, On the approximation of shortest common supersequences and longest common subsequences, Multiway cuts in directed and node weighted graphs, Proving completeness by logic, Complexity and approximation ratio of semitotal domination in graphs, 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, Algorithmic aspects of total Roman {3}-domination in graphs, Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, Acyclic Matching in Some Subclasses of Graphs, Complexity and Polynomially Solvable Special Cases of QUBO, Improved approximations of independent sets in bounded-degree graphs, Recent results in hardness of approximation, Some recent strong inapproximability results, On approximation properties of the Independent set problem for degree 3 graphs, Approximation of Constraint Satisfaction via local search, Parameterized Complexity of Multi-Node Hubs, On Geometric Set Cover for Orthants, Definable Inapproximability: New Challenges for Duplicator, 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, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, 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, Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions, Computational study of a branching algorithm for the maximum \(k\)-cut problem, Acyclic matching in some subclasses of graphs, Probabilistic nonunitary gate in imaginary time evolution, On the approximation hardness of geodetic set and its variants, A semidefinite relaxation based global algorithm for two-level graph partition problem, 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, 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, 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, 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, Algorithmic aspects of total Roman and total double Roman domination in graphs, 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, Unnamed Item, The Maximum k-Colorable Subgraph Problem and Related Problems, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, On the approximability of some maximum spanning tree problems, Graph layout problems, Intractability of assembly sequencing: Unit disks in the plane, Quantum Annealing versus Digital Computing, An Exact Method for the Minimum Feedback Arc Set Problem, Maximum Cut Parameterized by Crossing Number, Max-independent set and the quantum alternating operator ansatz, New Valid Inequalities for the Optimal Communication Spanning Tree Problem, 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, 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, Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs, A Logical Approach to Constraint Satisfaction, Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph, Unnamed Item, Unnamed Item, When polynomial approximation meets exact computation, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, When polynomial approximation meets exact computation, 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, The temporal explorer who returns to the base, On the complexity of minimum maximal uniquely restricted matching, Lower bounds for the happy coloring problems, Approximability of covering cells with line segments, Near optimal multiple alignment within a band in polynomial time, Linear game non-contextuality and Bell inequalities—a graph-theoretic approach, Algorithmic complexity of weakly connected Roman domination in graphs, Stackelberg Max Closure with Multiple Followers, Unnamed Item, Algorithmic aspects of small quasi-kernels, On the computational complexity of Roman\(\{2\}\)-domination in grid graphs, Algorithms for maximizing monotone submodular function minus modular function under noise, MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, On parallel versus sequential approximation, On the kernel and related problems in interval digraphs, Exact algorithms and hardness results for geometric red-blue hitting set problem, Algorithmic results on locating-total domination in graphs, Algorithmic results in Roman dominating functions on graphs, On the complexity of minimum maximal acyclic matchings, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Complexity of maximum cut on interval graphs, Online and Approximate Network Construction from Bounded Connectivity Constraints, Algorithmic aspects of total Roman ${2}$-domination in graphs, 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, Minimizing the number of switch instances on a flexible machine in polynomial time, Metabolic networks are NP-hard to reconstruct, \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel, Submodular unsplittable flow on trees, 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, 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)\), Solving the optimum communication spanning tree problem, On some tractable and hard instances for partial incentives and target set selection, 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, Smooth and strong PCPs, Algorithmic aspects of upper edge domination, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, Approximability of open \(k\)-monopoly problems, Algorithmic aspects of Roman domination in graphs, Double vertex-edge domination in graphs: complexity and algorithms, Positive influence domination in graphs, Bicriteria streaming algorithms to balance gain and cost with cardinality constraint, Parameterized complexity of multi-node hubs, A note on the satisfactory partition problem: constant size requirement, Classical symmetries and the quantum approximate optimization algorithm, On the complexity of minimum \(q\)-domination partization problems, Algorithmic results in secure total dominating sets on graphs, On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint, On computational capabilities of Ising machines based on nonlinear oscillators, Asymptotically quasi-optimal cryptography, A class of spectral bounds for max \(k\)-cut, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, The generalized definitions of the two-dimensional largest common substructure problems, Independent sets in Line of Sight networks, Algorithm and hardness results on neighborhood total domination in graphs, Greed is good for deterministic scale-free networks, PCPs and the hardness of generating synthetic data, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, A branch-and-bound algorithm for solving max-\(k\)-cut problem, On the geometric red-blue set cover problem, 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, Algorithmic aspects of upper paired-domination in graphs, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Minimum fill-in: inapproximability and almost tight lower bounds, Assortment planning for multiple chain stores, Algorithm and hardness results on hop domination in graphs, 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
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