Articles under category:
Approximation Algorithms
Approximation Algorithms
Vol 20, Article 6 (pp 1-23)
On a Generalization of Iterated and Randomized Rounding
by Nikhil Bansal
On a Generalization of Iterated and Randomized Rounding
by Nikhil Bansal
Vol 18, Article 18 (pp 1-19)
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks
by Chandra Chekuri and Tanmay Inamdar
Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks
by Chandra Chekuri and Tanmay Inamdar
Vol 18, Article 7 (pp 1-24)
[APRX-RND19 Spec Issue]
Fast and Deterministic Approximations for $k$-Cut
by Kent Quanrud
Fast and Deterministic Approximations for $k$-Cut
by Kent Quanrud
Vol 18, Article 3 (pp 1-29)
[APRX-RND16 Spec Issue]
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$
by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan
Vol 16, Article 14 (pp 1-8)
[NOTE]
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem
by Chandra Chekuri and Shi Li
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem
by Chandra Chekuri and Shi Li
Vol 16, Article 12 (pp 1-18)
Optimality of Correlated Sampling Strategies
by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan
Optimality of Correlated Sampling Strategies
by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan
Vol 14, Article 10 (pp 1-33)
[CCC17 Spec Issue]
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
by Mrinalkanti Ghosh and Madhur Tulsiani
Vol 14, Article 8 (pp 1-35)
The Complexity of Computing the Optimal Composition of Differential Privacy
by Jack Murtagh and Salil Vadhan
The Complexity of Computing the Optimal Composition of Differential Privacy
by Jack Murtagh and Salil Vadhan
Vol 14, Article 3 (pp 1-21)
[CCC17 Spec Issue]
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
A Deterministic PTAS for the Commutative Rank of Matrix Spaces
by Markus Bläser, Gorav Jindal, and Anurag Pandey
Vol 13, Article 15 (pp 1-24)
Tight Hardness of the Non-Commutative Grothendieck Problem
by Jop Briët, Oded Regev, and Rishi Saket
Tight Hardness of the Non-Commutative Grothendieck Problem
by Jop Briët, Oded Regev, and Rishi Saket
Vol 13, Article 14 (pp 1-17)
[APRX-RND15 Spec Issue]
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
by David Felber and Rafail Ostrovsky
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
by David Felber and Rafail Ostrovsky
Vol 13, Article 13 (pp 1-31)
Nash Equilibria in Perturbation-Stable Games
by Maria-Florina Balcan and Mark Braverman
Nash Equilibria in Perturbation-Stable Games
by Maria-Florina Balcan and Mark Braverman
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Vol 13, Article 5 (pp 1-47)
[APRX-RND13 Spec Issue]
A Pseudo-Approximation for the Genus of Hamiltonian Graphs
by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos
A Pseudo-Approximation for the Genus of Hamiltonian Graphs
by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos
Vol 12, Article 17 (pp 1-25)
[APRX-RND14 Spec Issue]
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
by Anand Louis and Yury Makarychev
Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion
by Anand Louis and Yury Makarychev
Vol 12, Article 15 (pp 1-29)
[APRX-RND14 Spec Issue]
Lowest-Degree $k$-Spanner: Approximation and Hardness
by Eden Chlamtáč and Michael Dinitz
Lowest-Degree $k$-Spanner: Approximation and Hardness
by Eden Chlamtáč and Michael Dinitz
Vol 12, Article 14 (pp 1-14)
[APRX-RND15 Spec Issue]
Minimizing Maximum Flow-Time on Related Machines
by Nikhil Bansal and Bouke Cloostermans
Minimizing Maximum Flow-Time on Related Machines
by Nikhil Bansal and Bouke Cloostermans
Vol 12, Article 2 (pp 1-34)
Lattice Sparsification and the Approximate Closest Vector Problem
by Daniel Dadush and Gábor Kun
Lattice Sparsification and the Approximate Closest Vector Problem
by Daniel Dadush and Gábor Kun
Vol 11, Article 9 (pp 241-256)
[APRX-RND13 Spec Issue]
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
by Shayan Oveis Gharan and Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
by Shayan Oveis Gharan and Luca Trevisan
Vol 11, Article 7 (pp 221-235)
[APRX-RND12 Spec Issue]
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
by Dana Moshkovitz
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
by Dana Moshkovitz
Vol 11, Article 4 (pp 105-147)
Maximizing the Spread of Influence through a Social Network
by David Kempe, Jon Kleinberg, and Éva Tardos
Maximizing the Spread of Influence through a Social Network
by David Kempe, Jon Kleinberg, and Éva Tardos
Vol 10, Article 13 (pp 341-358)
[APRX-RND12 Spec Issue]
Approximation Algorithm for Non-Boolean Max-$k$-CSP
by Konstantin Makarychev and Yury Makarychev
Approximation Algorithm for Non-Boolean Max-$k$-CSP
by Konstantin Makarychev and Yury Makarychev
Vol 10, Article 11 (pp 257-295)
Efficient Rounding for the Noncommutative Grothendieck Inequality
by Assaf Naor, Oded Regev, and Thomas Vidick
Efficient Rounding for the Noncommutative Grothendieck Inequality
by Assaf Naor, Oded Regev, and Thomas Vidick
Vol 9, Article 28 (pp 863-887)
[Boolean Spec Issue]
A Two-Prover One-Round Game with Strong Soundness
by Subhash Khot and Muli Safra
A Two-Prover One-Round Game with Strong Soundness
by Subhash Khot and Muli Safra
Vol 9, Article 22 (pp 685-702)
Hamming Approximation of NP Witnesses
by Daniel Sheldon and Neal E. Young
Hamming Approximation of NP Witnesses
by Daniel Sheldon and Neal E. Young
Vol 8, Article 26 (pp 597-622)
A Constant-Factor Approximation Algorithm for Co-clustering
by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar
A Constant-Factor Approximation Algorithm for Co-clustering
by Aris Anagnostopoulos, Anirban Dasgupta, and Ravi Kumar
Vol 8, Article 24 (pp 533-565)
Solving Packing Integer Programs via Randomized Rounding with Alterations
by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan
Solving Packing Integer Programs via Randomized Rounding with Alterations
by Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan
Vol 8, Article 20 (pp 429-460)
[Motwani Special Issue]
Budget-Constrained Auctions with Heterogeneous Items
by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala
Budget-Constrained Auctions with Heterogeneous Items
by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala
Vol 8, Article 18 (pp 401-413)
[Motwani Special Issue]
An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
by Julia Chuzhoy and Sanjeev Khanna
An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
by Julia Chuzhoy and Sanjeev Khanna
Vol 8, Article 14 (pp 321-350)
[Motwani Special Issue]
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
by Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
by Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani
Vol 7, Article 5 (pp 49-74)
Metric Clustering via Consistent Labeling
by Robert Krauthgamer and Tim Roughgarden
Metric Clustering via Consistent Labeling
by Robert Krauthgamer and Tim Roughgarden
Vol 7, Article 3 (pp 27-43)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
by Per Austrin, Subhash Khot, and Muli Safra
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
by Per Austrin, Subhash Khot, and Muli Safra
Vol 5, Article 4 (pp 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
Vol 4, Article 9 (pp 191-193)
[COMMENT]
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem
by Viswanath Nagarajan
On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem
by Viswanath Nagarajan
Vol 4, Article 2 (pp 21-51)
Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem
by Miklós Ajtai
Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem
by Miklós Ajtai
Vol 4, Article 1 (pp 1-20)
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall
Vol 3, Article 10 (pp 197-209)
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
by Chandra Chekuri and Martin Pál
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
by Chandra Chekuri and Martin Pál
■
Vol 3, Article 9 (pp 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing
by Maria-Florina Balcan and Avrim Blum
Approximation Algorithms and Online Mechanisms for Item Pricing
by Maria-Florina Balcan and Avrim Blum
Vol 3, Article 6 (pp 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman
Vol 3, Article 3 (pp 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Vol 2, Article 13 (pp 249-266)
Correlation Clustering with a Fixed Number of Clusters
by Ioannis Giotis and Venkatesan Guruswami
Correlation Clustering with a Fixed Number of Clusters
by Ioannis Giotis and Venkatesan Guruswami
Vol 2, Article 12 (pp 225-247)
Matrix Approximation and Projective Clustering via Volume Sampling
by Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang
Matrix Approximation and Projective Clustering via Volume Sampling
by Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang
Vol 2, Article 11 (pp 207-224)
Embedding the Ulam metric into ℓ1
by Moses Charikar and Robert Krauthgamer
Embedding the Ulam metric into ℓ1
by Moses Charikar and Robert Krauthgamer
Vol 2, Article 7 (pp 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd
Vol 2, Article 4 (pp 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
Vol 2, Article 3 (pp 53-64)
An Improved Approximation Ratio for the Covering Steiner Problem
by Anupam Gupta and Aravind Srinivasan
An Improved Approximation Ratio for the Covering Steiner Problem
by Anupam Gupta and Aravind Srinivasan
Vol 2, Article 2 (pp 19-51)
Proving Integrality Gaps without Knowing the Linear Program
by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis
Proving Integrality Gaps without Knowing the Linear Program
by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis
Vol 1, Article 7 (pp 119-148)
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot