On the approximability of clique and related maximization problems
type: Item
instance of: scholarly article
title: On the approximability of clique and related maximization problems
zbMATH Open document ID: 1114.68427
DOI: 10.1016/S0022-0000(03)00110-7
author: Aravind Srinivasan
published in: Journal of Computer and System Sciences
publication date: 2004-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 2092865
zbMATH Keywords: Inapproximability
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Clique
zbMATH Keywords: Independent set
zbMATH Keywords: Packing
zbMATH Keywords: integer programs
zbMATH Keywords: Random sampling
MaRDI profile type: Publication
cites work: Q4945528
cites work: Proof verification and the hardness of approximation problems
cites work: Probabilistic checking of proofs
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Q2754129
cites work: Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Time-space tradeoffs for satisfiability
cites work: Q4400840
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Q2754130
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
cites work: A PCP characterization of NP with optimal amortized query complexity
cites work: Chernoff–Hoeffding Bounds for Applications with Limited Independence
cites work: Improved Approximation Guarantees for Packing and Covering Integer Programs
description: scientific article; zbMATH DE number 2092865