Chaitanya Swamy

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2022

A constant-factor approximation for directed latency in quasi-polynomial time.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

A Simple Approximation Algorithm for Vector Scheduling and Applications to Stochastic Min-Norm Load Balancing.

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

2021

On the Randomized Metric Distortion Conjecture.

[BibT_eX]

[DOI]

Haripriya Pulyassary

CoRR, 2021

Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Special Section on the Fifty-Eighth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017).

[BibT_eX]

[DOI]

Valentine Kabanets

Sofya Raskhodnikova

SIAM J. Comput., 2020

Approximate multi-matroid intersection via iterative refinement.

[BibT_eX]

[DOI]

Math. Program., 2020

Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Black-box reductions for cost-sharing mechanism design.

[BibT_eX]

[DOI]

Konstantinos Georgiou

Games Econ. Behav., 2019

Achieving target equilibria in network routing games without knowing the latency functions.

[BibT_eX]

[DOI]

Games Econ. Behav., 2019

Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions.

[BibT_eX]

[DOI]

André Linhares

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Approximation algorithms for minimum norm and ordered optimization problems.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Simpler and Better Algorithms for Minimum-Norm Load Balancing.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Approximation Algorithms for Minimum-Load <i>k</i>-Facility Location.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

ACM Trans. Algorithms, 2018

Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems.

[BibT_eX]

[DOI]

André Linhares

Math. Program., 2018

Minimizing Latency in Online Ride and Delivery Services.

[BibT_eX]

[DOI]

Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

Orienteering Algorithms for Generating Travel Itineraries.

[BibT_eX]

[DOI]

Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 2018

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Algorithms for Inverse Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Min-Max Theorems for Packing and Covering Odd (u, v)-trails.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Compact, Provably-Good LPs for Orienteering and Regret-Bounded Vehicle Routing.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Improved Algorithms for MST and Metric-TSP Interdiction.

[BibT_eX]

[DOI]

André Linhares

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

On the Integrality Gap of the Prize-Collecting Steiner Forest LP.

[BibT_eX]

[DOI]

Jochen Könemann

Neil Olver

Kanstantsin Pashkovich

R. Ravi

Jens Vygen

Proceedings of the Approximation, 2017

2016

Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems.

[BibT_eX]

[DOI]

Math. Oper. Res., 2016

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers.

[BibT_eX]

[DOI]

Sara Ahmadian

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players.

[BibT_eX]

[DOI]

Hadi Minooei

ACM Trans. Economics and Comput., 2015

Near-Optimal Hardness Results for Signaling in Bayesian Games.

[BibT_eX]

[DOI]

CoRR, 2015

Computing Optimal Tolls in Routing Games without Knowing the Latency Functions.

[BibT_eX]

[DOI]

Siddharth Barman

Umang Bhaskar

CoRR, 2015

Learning Arbitrary Statistical Mixtures of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract).

[BibT_eX]

[DOI]

Ian Post

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Improved Region-Growing and Combinatorial Algorithms for <i>k</i>-Route Cut Problems (Extended Abstract).

[BibT_eX]

[DOI]

Guru Guruganesh

Laura Sanità

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems.

[BibT_eX]

[DOI]

Ian Post

CoRR, 2014

Improved Region-Growing and Combinatorial Algorithms for $k$-Route Cut Problems.

[BibT_eX]

[DOI]

Guru Guruganesh

Laura Sanità

CoRR, 2014

Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Learning mixtures of arbitrary distributions over large discrete domains.

[BibT_eX]

[DOI]

Yuval Rabani

Leonard J. Schulman

Proceedings of the Innovations in Theoretical Computer Science, 2014

Welfare maximization and truthfulness in mechanism design with ordinal preferences.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Approximation Algorithms for Minimum-Load k-Facility Location.

[BibT_eX]

[DOI]

Mohammad R. Salavatipour

Proceedings of the Approximation, 2014

2013

Local-Search based Approximation Algorithms for Mobile Facility Location Problems.

[BibT_eX]

[DOI]

Sara Ahmadian

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

The effectiveness of stackelberg strategies and tolls for network congestion games.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

LP-based approximation algorithms for capacitated facility location.

[BibT_eX]

[DOI]

Retsef Levi

Math. Program., 2012

The effectiveness of lloyd-type methods for the k-means problem.

[BibT_eX]

[DOI]

J. ACM, 2012

Approximability of the Firefighter Problem - Computing Cuts over Time.

[BibT_eX]

[DOI]

Elliot Anshelevich

Ameya Hate

Algorithmica, 2012

Truthful Mechanism Design for Multidimensional Covering Problems.

[BibT_eX]

[DOI]

Hadi Minooei

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Improved Approximation Guarantees for Lower-Bounded Facility Location.

[BibT_eX]

[DOI]

Sara Ahmadian

Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

2011

Truthful and Near-Optimal Mechanism Design via Linear Programming.

[BibT_eX]

[DOI]

Ron Lavi

J. ACM, 2011

Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

2010

Approximation Algorithms for Non-single-minded Profit-Maximization Problems with Limited Supply.

[BibT_eX]

[DOI]

Khaled M. Elbassioni

Mahmoud Fouz

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm.

[BibT_eX]

[DOI]

Jaroslaw Byrka

Aravind Srinivasan

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

Truthful mechanism design for multidimensional scheduling via cycle monotonicity.

[BibT_eX]

[DOI]

Ron Lavi

Games Econ. Behav., 2009

Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity.

[BibT_eX]

[DOI]

Elliot Anshelevich

Ameya Hate

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Fault-tolerant facility location.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Approximation Algorithms for Data Placement Problems.

[BibT_eX]

[DOI]

Ivan D. Baev

Rajmohan Rajaraman

SIAM J. Comput., 2008

Optimal Power-Down Strategies.

[BibT_eX]

[DOI]

John Augustine

Sandy Irani

SIAM J. Comput., 2008

Algorithms for Probabilistically-Constrained Models of Risk-Averse Stochastic Optimization with Black-Box Distributions

[BibT_eX]

[DOI]

CoRR, 2008

Approximation algorithms for labeling hierarchical taxonomies.

[BibT_eX]

[DOI]

Yuval Rabani

Leonard J. Schulman

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply.

[BibT_eX]

[DOI]

Maurice Cheung

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Approximation algorithms for prize collecting forest problems with submodular penalty functions.

[BibT_eX]

[DOI]

Yogeshwer Sharma

David P. Williamson

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity.

[BibT_eX]

[DOI]

Ron Lavi

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization.

[BibT_eX]

[DOI]

Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

2006

Approximation algorithms for 2-stage stochastic optimization problems.

[BibT_eX]

[DOI]

SIGACT News, 2006

An approximation scheme for stochastic linear programming and its application to stochastic integer programs.

[BibT_eX]

[DOI]

J. ACM, 2006

Approximation Algorithms for Graph Homomorphism Problems.

[BibT_eX]

[DOI]

Michael Langberg

Yuval Rabani

Proceedings of the Approximation, 2006

2005

Network design for information networks.

[BibT_eX]

[DOI]

Ara Hayrapetyan

Éva Tardos

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sampling-based Approximation Algorithms for Multi-stage Stochastic.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

2004

Approximation Algorithms for Clustering Problems.

[BibT_eX]

PhD thesis, 2004

Primal-Dual Algorithms for Connected Facility Location Problems.

[BibT_eX]

[DOI]

Amit Kumar

Algorithmica, 2004

Correlation Clustering: maximizing agreements via semidefinite programming.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Facility location with Service Installation Costs.

[BibT_eX]

[DOI]

Retsef Levi

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Stochastic Optimization is (Almost) as easy as Deterministic Optimization.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

1999

A Randomized Algorithm for Flow Shop Scheduling.

[BibT_eX]

[DOI]

Naveen Garg

Sachin Jain