Clique is hard to approximate within \(n^{1-\epsilon}\)
From MaRDI portal
Publication:1588908
DOI10.1007/BF02392825zbMath0989.68060WikidataQ56210419 ScholiaQ56210419MaRDI QIDQ1588908
Publication date: 6 December 2000
Published in: Acta Mathematica (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
Packing Under Convex Quadratic Constraints ⋮ Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems ⋮ Ultimate greedy approximation of independent sets in subcubic graphs ⋮ Analysis of MILP Techniques for the Pooling Problem ⋮ Independent Sets in Restricted Line of Sight Networks ⋮ On approximating MIS over B1-VPG graphs* ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Combinatorial Auctions with Conflict-Based Externalities ⋮ On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Independent sets in asteroidal triple-free graphs ⋮ Estimating the Size of Branch-and-Bound Trees ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ Inductive graph invariants and approximation algorithms ⋮ Inapproximability of Maximum Weighted Edge Biclique and Its Applications ⋮ Geometric Packing under Nonuniform Constraints ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ Elliptic polytopes and invariant norms of linear operators ⋮ Unnamed Item ⋮ Spectrum Bidding in Wireless Networks and Related ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ Scheduling with machine conflicts ⋮ Advice complexity of adaptive priority algorithms ⋮ Expander graphs and their applications ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Introduction to Testing Graph Properties ⋮ Problems on One Way Road Networks ⋮ The Approximability of Assortment Optimization Under Ranking Preferences ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ APPROXIMATING THE MEAN SPEEDUP IN TRACE MONOIDS ⋮ The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ A guide to conic optimisation and its applications ⋮ Near Approximation of Maximum Weight Matching through Efficient Weight Reduction ⋮ Recoverable Values for Independent Sets ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ In)approximability of Maximum Minimal FVS ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Approximating Independent Set and Coloring in Random Uniform Hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Turán’s Theorem Through Algorithmic Lens ⋮ Algorithms approaching the threshold for semi-random planted clique ⋮ Mining relevant information on the Web: a clique-based approach ⋮ A priori optimization for the probabilistic maximum independent set problem ⋮ Algorithm for optimal winner determination in combinatorial auctions ⋮ Inapproximability of finding maximum hidden sets on polygons and terrains ⋮ Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems ⋮ Algorithms and hardness for the longest common subsequence of three strings and related problems ⋮ Pattern masking for dictionary matching: theory and practice ⋮ Open packing in \(H\)-free graphs and subclasses of split graphs ⋮ Reformulations and complexity of the clique interdiction problem by graph mapping ⋮ Robust Independence Systems ⋮ Finding a Dense-Core in Jellyfish Graphs ⋮ Graphs with degree sequence \(\{ ( m - 1 )^m , ( n - 1 )^n \}\) and \(\{ m^n , n^m \}\) ⋮ Global equilibrium search applied to the unconstrained binary quadratic optimization problem ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Overflow management with self-eliminations ⋮ Testing for Dense Subsets in a Graph via the Partition Function ⋮ Coloring tournaments with few colors: algorithms and complexity ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ A metaheuristic algorithm for large maximum weight independent set problems ⋮ Anchor-robust project scheduling with non-availability periods ⋮ Overflow management with self-eliminations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs ⋮ Short Locally Testable Codes and Proofs ⋮ Introduction to Testing Graph Properties ⋮ DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ On the Approximability of Some Haplotyping Problems ⋮ Approximation in (Poly-) Logarithmic Space ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ Enumerating Isolated Cliques in Synthetic and Financial Networks ⋮ Unnamed Item ⋮ Leafy spanning arborescences in DAGs ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction* ⋮ A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem ⋮ Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ Independent sets in semi-random hypergraphs ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ An options-based solution to the sequential auction problem ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ A lower bound on the independence number of a graph in terms of degrees and local clique sizes ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- On the complexity of approximating the independent set problem
- Optimization, approximation, and complexity classes
- Approximating maximum independent sets by excluding subgraphs
- Approximation algorithms for combinatorial problems
- On the power of multi-prover interactive protocols
- Improved non-approximability results
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- Linearity testing in characteristic two
- The Knowledge Complexity of Interactive Proof Systems
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Two-Prover Protocols---Low Error at Affordable Rates
- Efficient probabilistically checkable proofs and applications to approximations
- On Unapproximable Versions of $NP$-Complete Problems
This page was built for publication: Clique is hard to approximate within \(n^{1-\epsilon}\)
