Articles under category:
Algorithms
Algorithms
ToC Library Graduate Surveys 9 (2020) 100 pages
A Survey on Distribution Testing: Your Data is Big. But is it Blue?
by Clément L. Canonne
A Survey on Distribution Testing: Your Data is Big. But is it Blue?
by Clément L. Canonne
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 19, Article 8 (pp 1-71)
[APRX-RND20 Spec Issue]
Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
by Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
by Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
Vol 19, Article 2 (pp 1-23)
On Solving Reachability in Grid Digraphs using a Pseudoseparator
by Rahul Jain and Raghunath Tewari
On Solving Reachability in Grid Digraphs using a Pseudoseparator
by Rahul Jain and Raghunath Tewari
Vol 19, Article 1 (pp 1-48)
Sublinear-Time Computation in the Presence of Online Erasures
by Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma
Sublinear-Time Computation in the Presence of Online Erasures
by Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma
Vol 18, Article 23 (pp 1-24)
Pure Entropic Regularization for Metrical Task Systems
by Christian Coester and James R. Lee
Pure Entropic Regularization for Metrical Task Systems
by Christian Coester and James R. Lee
Vol 18, Article 20 (pp 1-32)
Universal Streaming of Subset Norms
by Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang
Universal Streaming of Subset Norms
by Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang
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 9 (pp 1-18)
[APRX-RND19 Spec Issue]
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
by Zongchen Chen and Santosh S. Vempala
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
by Zongchen Chen and Santosh S. Vempala
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 6 (pp 1-33)
[APRX-RND19 Spec Issue]
Max-Min Greedy Matching
by Alon Eden, Uriel Feige, and Michal Feldman
Max-Min Greedy Matching
by Alon Eden, Uriel Feige, and Michal Feldman
Vol 17, Article 5 (pp 1-27)
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
Vol 16, Article 15 (pp 1-25)
[APRX-RND16 Spec Issue]
Online Row Sampling
by Michael B. Cohen, Cameron Musco, and Jakub Pachocki
Online Row Sampling
by Michael B. Cohen, Cameron Musco, and Jakub Pachocki
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 16, Article 3 (pp 1-36)
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri
Vol 15, Article 21 (pp 1-27)
The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
by Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
by Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett
Vol 15, Article 15 (pp 1-58)
[APRX-RND16 Spec Issue]
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
by Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
by Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov
Vol 15, Article 7 (pp 1-36)
Randomized Polynomial-Time Identity Testing for Noncommutative Circuits
by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja
Randomized Polynomial-Time Identity Testing for Noncommutative Circuits
by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja
Vol 15, Article 4 (pp 1-32)
[RESEARCH SURVEY]
Potential-Function Proofs for Gradient Methods
by Nikhil Bansal and Anupam Gupta
Potential-Function Proofs for Gradient Methods
by Nikhil Bansal and Anupam Gupta
Vol 14, Article 14 (pp 1-29)
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
by Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
by Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
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 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 14, Article 1 (pp 1-27)
Linear-Time Algorithm for Quantum 2SAT
by Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang
Linear-Time Algorithm for Quantum 2SAT
by Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang
Vol 13, Article 21 (pp 1-38)
[CCC16 Spec Issue]
Decoding Reed–Muller Codes over Product Sets
by John Y. Kim and Swastik Kopparty
Decoding Reed–Muller Codes over Product Sets
by John Y. Kim and Swastik Kopparty
Vol 13, Article 20 (pp 1-25)
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
by F. Bruce Shepherd and Adrian R. Vetta
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
by F. Bruce Shepherd and Adrian R. Vetta
Vol 13, Article 19 (pp 1-51)
[APRX-RND15 Spec Issue]
Improved NP-Inapproximability for 2ドル$-Variable Linear Equations
by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright
Improved NP-Inapproximability for 2ドル$-Variable Linear Equations
by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright
Vol 13, Article 17 (pp 1-41)
A Constructive Lovász Local Lemma for Permutations
by David G. Harris and Aravind Srinivasan
A Constructive Lovász Local Lemma for Permutations
by David G. Harris and Aravind Srinivasan
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 8 (pp 1-22)
[APRX-RND15 Spec Issue]
The Minimum Bisection in the Planted Bisection Model
by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
The Minimum Bisection in the Planted Bisection Model
by Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
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 13, Article 2 (pp 1-21)
[CCC16 Spec Issue]
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
by Rohit Gurjar, Arpita Korwar, and Nitin Saxena
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
by Rohit Gurjar, Arpita Korwar, and Nitin Saxena
Vol 12, Article 18 (pp 1-35)
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester
by Cedric Yen-Yu Lin and Han-Hsuan Lin
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester
by Cedric Yen-Yu Lin and Han-Hsuan Lin
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 7 (pp 1-27)
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
by Swastik Kopparty, Mrinal Kumar, and Michael Saks
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
by Swastik Kopparty, Mrinal Kumar, and Michael Saks
Vol 12, Article 6 (pp 1-11)
[NOTE]
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee
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 16 (pp 403-412)
[NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Vol 11, Article 15 (pp 395-401)
[NOTE]
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Vol 11, Article 13 (pp 339-355)
Computing the Partition Function for Cliques in a Graph
by Alexander Barvinok
Computing the Partition Function for Cliques in a Graph
by Alexander Barvinok
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 11, Article 1 (pp 1-34)
The Complexity of Deciding Statistical Properties of Samplable Distributions
by Thomas Watson
The Complexity of Deciding Statistical Properties of Samplable Distributions
by Thomas Watson
Vol 10, Article 18 (pp 465-514)
On Reconstruction and Testing of Read-Once Formulas
by Amir Shpilka and Ilya Volkovich
On Reconstruction and Testing of Read-Once Formulas
by Amir Shpilka and Ilya Volkovich
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 12 (pp 297-339)
Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
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 10, Article 10 (pp 237-256)
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Vol 9, Article 30 (pp 897-945)
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream
by Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream
by Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan
Vol 9, Article 19 (pp 617-651)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
by Uriel Feige, Elchanan Mossel, and Dan Vilenchik
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
by Uriel Feige, Elchanan Mossel, and Dan Vilenchik
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 25 (pp 567-595)
[Motwani Special Issue]
Online Graph Edge-Coloring in the Random-Order Arrival Model
by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani
Online Graph Edge-Coloring in the Random-Order Arrival Model
by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani
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 19 (pp 415-428)
Distance Transforms of Sampled Functions
by Pedro F. Felzenszwalb and Daniel P. Huttenlocher
Distance Transforms of Sampled Functions
by Pedro F. Felzenszwalb and Daniel P. Huttenlocher
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 15 (pp 351-368)
[Motwani Special Issue]
One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk
by Ashish Goel and Ian Post
One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk
by Ashish Goel and Ian Post
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 8, Article 9 (pp 209-229)
[Motwani Special Issue]
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule
by Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule
by Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs
Vol 8, Article 7 (pp 165-195)
[Motwani Special Issue]
Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
by Chandra Chekuri, Sungjin Im, and Benjamin Moseley
Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
by Chandra Chekuri, Sungjin Im, and Benjamin Moseley
Vol 8, Article 6 (pp 121-164)
[RESEARCH SURVEY]
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
by Sanjeev Arora, Elad Hazan, and Satyen Kale
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
by Sanjeev Arora, Elad Hazan, and Satyen Kale
Vol 8, Article 4 (pp 69-94)
[Motwani Special Issue]
Regularity Lemmas and Combinatorial Algorithms
by Nikhil Bansal and R. Ryan Williams
Regularity Lemmas and Combinatorial Algorithms
by Nikhil Bansal and R. Ryan Williams
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 2 (pp 19-25)
[NOTE]
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Vol 6, Article 11 (pp 247-290)
The Submodular Welfare Problem with Demand Queries
by Uriel Feige and Jan Vondrák
The Submodular Welfare Problem with Demand Queries
by Uriel Feige and Jan Vondrák
Vol 6, Article 8 (pp 179-199)
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
by Avrim Blum, Eyal Even-Dar, and Katrina Ligett
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
by Avrim Blum, Eyal Even-Dar, and Katrina Ligett
Vol 6, Article 2 (pp 27-46)
Reordering Buffers for General Metric Spaces
by Matthias Englert, Harald Räcke, and Matthias Westermann
Reordering Buffers for General Metric Spaces
by Matthias Englert, Harald Räcke, and Matthias Westermann
Vol 5, Article 9 (pp 173-189)
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time
by Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time
by Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster
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 11 (pp 211-219)
The Randomized Communication Complexity of Set Disjointness
by Johan Håstad and Avi Wigderson
The Randomized Communication Complexity of Set Disjointness
by Johan Håstad and Avi Wigderson
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 8 (pp 159-177)
Removing Degeneracy May Require a Large Dimension Increase
by Jiří Matoušek and Petr Škovroň
Removing Degeneracy May Require a Large Dimension Increase
by Jiří Matoušek and Petr Škovroň
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 10 (pp 185-206)
Learning Restricted Models of Arithmetic Circuits
by Adam Klivans and Amir Shpilka
Learning Restricted Models of Arithmetic Circuits
by Adam Klivans and Amir Shpilka
Vol 2, Article 8 (pp 147-172)
On Learning Random DNF Formulas Under the Uniform Distribution
by Jeffrey C. Jackson and Rocco A. Servedio
On Learning Random DNF Formulas Under the Uniform Distribution
by Jeffrey C. Jackson and Rocco A. Servedio
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 6 (pp 105-117)
Combining Online Algorithms for Acceptance and Rejection
by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour
Combining Online Algorithms for Acceptance and Rejection
by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour