arXiv preprint ·
Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an approximation ratio of $N/2^{Ω(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{Ω((\log N)^{1/3})}$ obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form $\operatorname{Las}_{R(t)}(G)\ge2^{-t}N\Longrightarrowα(G)\ge2^t$, at $2^{o(\sqrt{\log N\log\log N})}$ levels, cannot hold over a range extending beyond $t=O(\sqrt{\log N\log\log N})$. Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of $\sqrt{\log\log N}$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Complexity of Value Optimization in Sporadic Task Systems
Impossibility of No-Regret in Multi-Agent Bidding
Linear Hashing Is Poissonesque
Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.