On the approximability of clique and related maximization problems

DOI10.1016/S0022-0000(03)00110-7zbMath1114.68427MaRDI QIDQ1877696

Aravind Srinivasan

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Packinginteger programsApproximation algorithmsIndependent setCliqueRandom samplingInapproximability

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (3)

Fast Heuristics and Approximation Algorithms ⋮ Unnamed Item ⋮ Hardness magnification near state-of-the-art lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Approximating maximum independent sets by excluding subgraphs
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Time-space tradeoffs for satisfiability
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Proof verification and the hardness of approximation problems
• A PCP characterization of NP with optimal amortized query complexity
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Improved Approximation Guarantees for Packing and Covering Integer Programs

This page was built for publication: On the approximability of clique and related maximization problems