Some optimal inapproximability results

DOI10.1145/502090.502098zbMath1127.68405OpenAlexW1999032440WikidataQ55879781 ScholiaQ55879781MaRDI QIDQ5441360

Publication date: 11 February 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/502090.502098

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Chromatic kernel and its applications, Towards optimal lower bounds for clique and chromatic number., Improved approximations for max set splitting and max NAE SAT, Approximation algorithms for aligning points, The inapproximability of lattice and coding problems with preprocessing, Sharp spectral bounds of several graph parameters using eigenvector norms, Inapproximability results for equations over finite groups, Hardness and approximation of traffic grooming, Hard constraint satisfaction problems have hard gaps at location 1, A note on unique games, Complexity of approximating CSP with balance/hard constraints, A nonmonotone GRASP, Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover, On the approximability of the maximum interval constrained coloring problem, An efficient fixed-parameter algorithm for 3-hitting set, Towards a characterization of constant-factor approximable finite-valued CSPs, Differential approximation of MIN SAT, MAX SAT and related problems, An FPTAS for optimizing a class of low-rank functions over a polytope, Reoptimization of constraint satisfaction problems with approximation resistant predicates, Maximum $H$-colourable subdigraphs and constraint optimization with arbitrary weights, Time-approximation trade-offs for inapproximable problems, Approximation for vertex cover in $\beta$-conflict graphs, Approximation algorithms for orienting mixed graphs, On approximating string selection problems with outliers, Approximation with a fixed number of solutions of some multiobjective maximization problems, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Approximation algorithm for a class of global optimization problems, On the configuration LP for maximum budgeted allocation, Non-approximability of weighted multiple sequence alignment., Welfare maximization with friends-of-friends network externalities, Energy efficient monitoring in sensor networks, A tighter upper bound for random MAX $2$-SAT, Intractability of min- and max-cut in streaming graphs, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, On the complexity of reconfiguration problems, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., More on average case vs approximation complexity, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Toward a model for backtracking and dynamic programming, Approximability of sparse integer programs, Minimizing worst-case and average-case makespan over scenarios, Performance tradeoffs in structured peer to peer streaming, Greedy $\varDelta $-approximation algorithm for covering with arbitrary constraints and submodular cost, Solving MAX-$r$-SAT above a tight lower bound, On the robust hardness of Gröbner basis computation, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, On the inapproximability of maximum intersection problems, Affine reductions for LPs and SDPs, A survey on the structure of approximation classes, Bisections of graphs, On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field, Approximate inference in Bayesian networks: parameterized complexity results, Modelling the dynamics of stochastic local search on $k$-SAT, On the complexity of optimization over the standard simplex, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, New inapproximability bounds for TSP, $K$-adaptability in stochastic combinatorial optimization under objective uncertainty, On extensions of the deterministic online model for bipartite matching and max-sat, Sums of squares based approximation algorithms for MAX-SAT, Quell, Complete partitions of graphs, Limited lookahead in imperfect-information games, Improved approximation algorithms for projection games, The Steiner tree problem on graphs: inapproximability results, Combinatorial network abstraction by trees and distances, On the lower bounds of random Max 3 and 4-SAT, Approximation hardness of dominating set problems in bounded degree graphs, Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games, The maximum labeled path problem, Approximating maximum satisfiable subsystems of linear equations of bounded width, Average-case analysis for the MAX-2SAT problem, On approximating the b-chromatic number, On the structure of Boolean functions with small spectral norm, Inapproximability results for equations over infinite groups, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2$k$-SAT, Recognizing frozen variables in constraint satisfaction problems, The approximability of non-Boolean satisfiability problems and restricted integer programming, A fault-containing self-stabilizing $(3-\frac 2{\varDelta+1})$-approximation algorithm for vertex cover in anonymous networks, The commuting local Hamiltonian problem on locally expanding graphs is approximable in $\mathsf{NP}$, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width, Complexity and approximation of finding the longest vector sum, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, New results on the complexity of deletion propagation, Approximation algorithms for balancing signed graphs, Probabilistic characterization of random Max $r$-Sat, A priori TSP in the scenario model, On non-optimally expanding sets in Grassmann graphs, Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor, Single machine precedence constrained scheduling is a Vertex cover problem, Minimal achievable approximation ratio for MAX-MQ in finite fields, Strong and weak edges of a graph and linkages with the vertex cover problem, A simple rounding scheme for multistage optimization, Dynamical noise sensitivity for the voter model, Using the method of conditional expectations to supply an improved starting point for CCLS, Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs, Classical symmetries and the quantum approximate optimization algorithm, The complexity of solving equations over finite groups, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, Improved approximation for orienting mixed graphs, Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Fast Heuristics and Approximation Algorithms, Simple analysis of graph tests for linearity and PCP, Fast Distributed Approximation for Max-Cut, Generalized XOR non-locality games with graph description on a square lattice, Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes, Quasi-Popular Matchings, Optimality, and Extended Formulations, Approximating the Spanning k-Tree Forest Problem, Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem, Nonlocal Games with Noisy Maximally Entangled States are Decidable, 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time, Online $L(2,1)$-coloring problem on paths with restricted size of memory, Max-3-Lin over non-abelian groups with universal factor graphs, Unnamed Item, Unnamed Item, Building a small and informative phylogenetic supertree, Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations, Pseudorandom sets in Grassmann graph have near-perfect expansion, Revisiting maximum satisfiability and related problems in data streams, Constrained Submodular Maximization via a Nonsymmetric Technique, Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, Exact enumeration of satisfiable 2-SAT formulae, Elliptic polytopes and invariant norms of linear operators, Unnamed Item, Unnamed Item, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Complexity of maximum cut on interval graphs, Approximating sparse quadratic programs, The Computational Complexity of the ChordLink Model, $(2+\varepsilon)$-Sat Is NP-hard, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Computing the Partition Function of a Polynomial on the Boolean Cube, Unnamed Item, An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices, A Characterization of hard-to-cover CSPs, Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices, Parallel Repetition of Two-Prover One-Round Games: An Exposition, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Unnamed Item, A Spectral Method for MAX2SAT in the Planted Solution Model, Approximation Algorithms for CSPs, Grothendieck’s Theorem, past and present, On the Lower Bounds of Random Max 3 and 4-SAT, Agnostic Learning from Tolerant Natural Proofs, Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph, On the Consistent Path Problem, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Fast Reed-Solomon Interactive Oracle Proofs of Proximity, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Revisiting alphabet reduction in Dinur’s PCP., On the Approximability of Presidential Type Predicates, Cones of multipowers and combinatorial optimization problems, Quantum computing, postselection, and probabilistic polynomial-time, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Query-Efficient Dictatorship Testing with Perfect Completeness, Composition of Low-Error 2-Query PCPs Using Decodable PCPs, Computational topology and the Unique Games Conjecture, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Tropical paths in vertex-colored graphs, Parallel and concurrent security of the HB and $HB^{+}$ protocols, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Complexity and algorithms for finding a subset of vectors with the longest sum, Energy Efficient Monitoring in Sensor Networks, The non-hardness of approximating circuit size, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, Extended formulations from communication protocols in output-efficient time, Definable Inapproximability: New Challenges for Duplicator, On the advantage over a random assignment, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, MAX k‐CUT and approximating the chromatic number of random graphs, Multitasking Capacity: Hardness Results and Improved Constructions, Online Submodular Maximization with Preemption, Unnamed Item, Imperfect gaps in Gap-ETH and PCPs, Distributed set cover approximation: Primal-dual with optimal locality, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM, The Complexity of Contracts, Propagation Connectivity of Random Hypergraphs, Unnamed Item, Introduction to the Maximum Solution Problem, The Quest for Strong Inapproximability Results with Perfect Completeness, Linear game non-contextuality and Bell inequalities—a graph-theoretic approach, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Hardness of Rainbow Coloring Hypergraphs, An Improved Dictatorship Test with Perfect Completeness, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, Computational Integrity with a Public Random String from Quasi-Linear PCPs, Revisiting maximum satisfiability and related problems in data streams, Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses, Mathematics of computation through the lens of linear equations and lattices, Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint, On regularity of Max-CSPs and Min-CSPs, Improved Parameterized Algorithms for above Average Constraint Satisfaction, Grothendieck-Type Inequalities in Combinatorial Optimization, Complexity of approximating bounded variants of optimization problems, Approximation hardness of edge dominating set problems, Simultaneous Approximation of Constraint Satisfaction Problems, Quantum Locally Testable Codes, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Inapproximability of maximum biclique problems, minimum $ k$-cut and densest at-least-$ k$-subgraph from the small set expansion hypothesis, Fuzzy covering problem of fuzzy graphs and its application to investigate the Indian economy in new normal, Short PCPPs verifiable in polylogarithmic time with $O(1)$ queries, Satisfiability Thresholds beyond k −XORSAT, Noisy tensor completion via the sum-of-squares hierarchy, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Adding cardinality constraints to integer programs with applications to maximum satisfiability, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Note on maximal split-stable subgraphs, Satisfiability with index dependency, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach, Column subset selection problem is UG-hard, A novel algorithm for Max Sat calling MOCE to order, On computational capabilities of Ising machines based on nonlinear oscillators, Supermodular functions and the complexity of MAX CSP, Quantum machine learning: a classical perspective, Weighted amplifiers and inapproximability results for travelling salesman problem, Judicious partitions of directed graphs, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, Covering problem on fuzzy graphs and its application in disaster management system, A query efficient non-adaptive long code test with perfect completeness, Parameterized complexity of satisfying almost all linear equations over $\mathbb F_2$, Improved approximation algorithms for the spanning star forest problem, Approximation hardness of graphic TSP on cubic graphs, On the Complexity of the Minimum Independent Set Partition Problem, An algebraic proof of the real number PCP theorem, On the (In)security of Kilian-based SNARGs, On the approximability of digraph ordering, Complexity and approximability of parameterized MAX-CSPs, Large cuts with local algorithms on triangle-free graphs, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, Inapproximability ratios for crossing number, Accelerating deep learning with memcomputing, Block Sorting Is APX-Hard, Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies, Complexity and approximability of extended spanning star forest problems in general and complete graphs, Super-polynomial approximation branching algorithms, Vertex cover in conflict graphs, Go-MOCE: greedy order method of conditional expectations for Max Sat, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, How to Encrypt with the LPN Problem, A priori TSP in the Scenario Model, Approximation algorithms for geometric conflict free covering problems, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, New exact algorithms for the 2-constraint satisfaction problem, PCPs and the hardness of generating synthetic data, Approximability of the dispersed $\vec{p}$-neighbor $k$-supplier problem, Quantitative relation between noise sensitivity and influences, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), On the Random Satisfiable Process, Finding an Unknown Acyclic Orientation of a Given Graph, Approximation Algorithms for Orienting Mixed Graphs, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Vertex cover might be hard to approximate to within $2 - \varepsilon $, Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms, Hedging uncertainty: approximation algorithms for stochastic optimization problems, TSP with bounded metrics, Parallel and Concurrent Security of the HB and HB + Protocols, Minimization problems for parity OBDDs, Max-bisections of $H$-free graphs, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, Inapproximability of b-Matching in k-Uniform Hypergraphs, Three-Player Entangled XOR Games are NP-Hard to Approximate, Robustly Solvable Constraint Satisfaction Problems, From Graph Orientation to the Unweighted Maximum Cut, Satisfying Degree-d Equations over GF[2 n], Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Short Locally Testable Codes and Proofs, Complexity results on planar multifacility location problems with forbidden regions, Quantum XOR Games, Learning Hurdles for Sleeping Experts, Approximate Kernel Clustering, Optimizing positional scoring rules for rank aggregation, Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms, On Khot’s unique games conjecture, Hypergraph cuts above the average, Eigenvector-based identification of bipartite subgraphs, Limitations of Deterministic Auction Design for Correlated Bidders, Clustering with qualitative information, On Dinur’s proof of the PCP theorem, Minimum Cell Connection in Line Segment Arrangements, ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS, Locally consistent constraint satisfaction problems, Hardness of approximation for knapsack problems, Covering Graphs by Colored Stable Sets, Oblivious algorithms for the maximum directed cut problem, Moderately exponential time and fixed parameter approximation algorithms, New limits of treewidth-based tractability in optimization