Some optimal inapproximability results
From MaRDI portal
Publication:5441360
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
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 (only showing first 100 items - show all)
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
This page was built for publication: Some optimal inapproximability results
