Anupam Gupta

Inbal Talgam-Cohen

CoRR, 2024

Max-Cut with ε-Accurate Predictions.

[BibT_eX]

[DOI]

CoRR, 2024

Poly-logarithmic Competitiveness for the k-Taxi Problem.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Set Covering with Our Eyes Wide Shut.

[BibT_eX]

[DOI]

Gregory Kehne

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Maintaining Matroid Intersections Online.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Corrigendum: Metric Embedding via Shortest Path Decompositions.

[BibT_eX]

[DOI]

SIAM J. Comput., October, 2023

Lipschitz Selectors May Not Yield Competitive Algorithms for Convex Body Chasing.

[BibT_eX]

[DOI]

C. J. Argue

Discret. Comput. Geom., October, 2023

Improving Length-Generalization in Transformers via Task Hinting.

[BibT_eX]

[DOI]

Pranjal Awasthi

CoRR, 2023

A Local Search-Based Approach for Set Covering.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Minimizing Completion Times for Stochastic Jobs via Batched Free Times.

[BibT_eX]

[DOI]

Rudy Zhou

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Configuration Balancing for Stochastic Requests.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Graph Searching with Predictions.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

The Price of Explainability for Clustering.

[BibT_eX]

[DOI]

Madhusudhan Reddy Pittu

Ola Svensson

Rachel Yuan

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Efficient Algorithms and Hardness Results for the Weighted k-Server Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Caching with Time Windows and Delays.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Metric Embedding via Shortest Path Decompositions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Stochastic makespan minimization in structured set systems.

[BibT_eX]

[DOI]

Math. Program., 2022

Optimal Bounds for the k-cut Problem.

[BibT_eX]

[DOI]

J. ACM, 2022

Online Discrepancy with Recourse for Vectors and Graphs.

[BibT_eX]

[DOI]

Vijaykrishna Gurunathan

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

An Improved Local Search Algorithm for k-Median.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Robust Secretary and Prophet Algorithms for Packing Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Learning from a Sample in Online Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions.

[BibT_eX]

[DOI]

Bernardo Subercaseaux

Kevin Sun

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Matroid-Based TSP Rounding for Half-Integral Solutions.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation.

[BibT_eX]

[DOI]

Rohan Ghuge

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Probing to Minimize.

[BibT_eX]

[DOI]

Weina Wang

Jalani Williams

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

Fair algorithms for selecting citizens' assemblies.

[BibT_eX]

[DOI]

Nat., 2021

Stochastic Load Balancing on Unrelated Machines.

[BibT_eX]

[DOI]

Math. Oper. Res., 2021

Chasing Convex Bodies with Linear Competitive Ratio.

[BibT_eX]

[DOI]

J. ACM, 2021

Random Order Set Cover is as Easy as Offline.

[BibT_eX]

[DOI]

Gregory Kehne

CoRR, 2021

A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut.

[BibT_eX]

[DOI]

CoRR, 2021

A quasipolynomial (2 + ε)-approximation for planar sparsest cut.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Chasing convex bodies with linear competitive ratio (invited paper).

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

The Connectivity Threshold for Dense Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Power of Adaptivity for Stochastic Submodular Cover.

[BibT_eX]

[DOI]

Rohan Ghuge

Proceedings of the 38th International Conference on Machine Learning, 2021

Structural Iterative Rounding for Generalized k-Median Problems.

[BibT_eX]

[DOI]

Rudy Zhou

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

Random Order Online Set Cover is as Easy as Offline.

[BibT_eX]

[DOI]

Gregory Kehne

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Bag-Of-Tasks Scheduling on Related Machines.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Optimal Bounds for the k-cut Problem.

[BibT_eX]

[DOI]

CoRR, 2020

Random-Order Models.

[BibT_eX]

[DOI]

CoRR, 2020

The Karger-Stein algorithm is optimal for k-cut.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Caching with time windows.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Online Submodular Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Neutralizing Self-Selection Bias in Sampling for Sortition.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Robust Algorithms for the Secretary Problem.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Online Carpooling Using Expander Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Fully-Dynamic Submodular Cover with Bounded Recourse.

[BibT_eX]

[DOI]

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

Dimension-Free Bounds for Chasing Convex Functions.

[BibT_eX]

[DOI]

C. J. Argue

Guru Guruganesh

Proceedings of the Conference on Learning Theory, 2020

Random-Order Models.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Potential-Function Proofs for Gradient Methods.

[BibT_eX]

[DOI]

Theory Comput., 2019

Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

The Number of Minimum k-Cuts: Improving the Karger-Stein Bound.

[BibT_eX]

[DOI]

CoRR, 2019

The number of minimum k-cuts: improving the Karger-Stein bound.

[BibT_eX]

[DOI]

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

Losing Treewidth by Separating Subsets.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Elastic Caching.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

k-Servers with a Smile: Online Algorithms via Projections.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Nearly-Linear Bound for Chasing Nested Convex Bodies.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

The Markovian Price of Information.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

Stochastic Online Metric Matching.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Tight FPT Approximations for k-Median and k-Means.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Non-Clairvoyant Precedence Constrained Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Better Algorithms for Stochastic Bandits with Adversarial Corruptions.

[BibT_eX]

[DOI]

Tomer Koren

Proceedings of the Conference on Learning Theory, 2019

2018

On the Lovász Theta Function for Independent Sets in Sparse Graphs.

[BibT_eX]

[DOI]

Guru Guruganesh

SIAM J. Comput., 2018

An FPT Algorithm Beating 2-Approximation for k-Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Local-Search Algorithm for Steiner Forest.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Maximizing Profit with Convex Costs in the Random-order Model.

[BibT_eX]

[DOI]

Ruta Mehta

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

Non-Preemptive Flow-Time Minimization via Rejections.

[BibT_eX]

[DOI]

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

Fully-Dynamic Bin Packing with Little Repacking.

[BibT_eX]

[DOI]

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

Faster Exact and Approximate Algorithms for k-Cut.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.

[BibT_eX]

[DOI]

Math. Oper. Res., 2017

Potential-Function Proofs for First-Order Methods.

[BibT_eX]

[DOI]

CoRR, 2017

Fully-Dynamic Bin Packing with Limited Repacking.

[BibT_eX]

[DOI]

CoRR, 2017

An FPT Algorithm Beating 2-Approximation for k-Cut.

[BibT_eX]

[DOI]

CoRR, 2017

Online and dynamic algorithms for set cover.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

LAST but not Least: Online Spanners for Buy-at-Bulk.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

Stochastic Unsplittable Flows.

[BibT_eX]

[DOI]

Archit Karandikar

Proceedings of the Approximation, 2017

2016

Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

On Hierarchical Routing in Doubling Metrics.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Algorithms for Hub Label Optimization.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online.

[BibT_eX]

[DOI]

Albert Gu

SIAM J. Comput., 2016

How the Experts Algorithm Can Help Solve LPs Online.

[BibT_eX]

[DOI]

Math. Oper. Res., 2016

An Improved Integrality Gap for Asymmetric TSP Paths.

[BibT_eX]

[DOI]

Zachary Friggstad

Mohit Singh

Math. Oper. Res., 2016

Algorithms and Adaptivity Gaps for Stochastic Probing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Approximation Algorithms for Aversion k-Clustering via Local k-Median.

[BibT_eX]

[DOI]

Guru Guruganesh

Melanie Schmidt

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

Online Algorithms for Covering and Packing Problems with Convex Objectives.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Pure Exploration of Multi-armed Bandit Under Matroid Constraints.

[BibT_eX]

[DOI]

Lijie Chen

Jian Li

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Efficient cost-sharing mechanisms for prize-collecting problems.

[BibT_eX]

[DOI]

Math. Program., 2015

Running Errands in Time: Approximation Algorithms for Stochastic Orienteering.

[BibT_eX]

[DOI]

Math. Oper. Res., 2015

Greedy Algorithms for Steiner Forest.

[BibT_eX]

[DOI]

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

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs.

[BibT_eX]

[DOI]

Kevin Schewior

Clifford Stein

Proceedings of the Approximation, 2015

2014

Vertex Sparsifiers: New Results from Old Techniques.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Thresholded covering algorithms for robust and max-min optimization.

[BibT_eX]

[DOI]

Math. Program., 2014

Approximating Sparse Covering Integer Programs Online.

[BibT_eX]

[DOI]

Math. Oper. Res., 2014

Online Packing and Covering Framework with Convex Objectives.

[BibT_eX]

[DOI]

CoRR, 2014

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching.

[BibT_eX]

[DOI]

Algorithmica, 2014

Minimum d-dimensional arrangement with fixed points.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Maintaining Assignments Online: Matching, Scheduling, and Flows.

[BibT_eX]

[DOI]

Cliff Stein

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Online Steiner Tree with Deletions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Towards (1 + ∊)-Approximate Flow Sparsifiers.

[BibT_eX]

[DOI]

Alexandr Andoni

Robert Krauthgamer

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Changing Bases: Multistage Optimization for Matroids and Matchings.

[BibT_eX]

[DOI]

Udi Wieder

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

How Experts Can Solve LPs Online.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

2013

Privately Releasing Conjunctions and the Statistical Query Barrier.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Set Covering with Our Eyes Closed.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Clustering under approximation stability.

[BibT_eX]

[DOI]

Maria-Florina Balcan

Avrim Blum

J. ACM, 2013

Random Rates for 0-Extension and Low-Diameter Decompositions.

[BibT_eX]

[DOI]

CoRR, 2013

Minimum d-dimensional arrangement with fixed points.

[BibT_eX]

[DOI]

CoRR, 2013

Towards (1+ε)-Approximate Flow Sparsifiers.

[BibT_eX]

[DOI]

Alexandr Andoni

Robert Krauthgamer

CoRR, 2013

Sparsest cut on bounded treewidth graphs: algorithms and hardness results.

[BibT_eX]

[DOI]

David Witmer

Proceedings of the Symposium on Theory of Computing Conference, 2013

Harnessing the power of two crossmatches.

[BibT_eX]

[DOI]

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Thrifty Algorithms for Multistage Robust Optimization.

[BibT_eX]

[DOI]

Vijay V. Vazirani

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

A Stochastic Probing Problem with Applications.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Packing Interdiction and Partial Covering Problems.

[BibT_eX]

[DOI]

Michael Dinitz

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Catch them if you can: how to serve impatient users.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

The Approximability of the Binary Paintshop Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Online and Stochastic Survivable Network Design.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Approximating TSP on Metrics with Bounded Global Growth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Technical Note - Approximation Algorithms for VRP with Stochastic Demands.

[BibT_eX]

[DOI]

Oper. Res., 2012

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings.

[BibT_eX]

[DOI]

Algorithmica, 2012

Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling.

[BibT_eX]

[DOI]

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

Iterative Constructions and Private Data Release.

[BibT_eX]

[DOI]

Aaron Roth

Jonathan R. Ullman

Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design.

[BibT_eX]

[DOI]

Guy E. Blelloch

Kanat Tangwongsan

Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Approximation algorithms for stochastic orienteering.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Scheduling heterogeneous processors isn't as easy as you think.

[BibT_eX]

[DOI]

Sungjin Im

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Multicast Routing for Energy Minimization Using Speed Scaling.

[BibT_eX]

[DOI]

Cliff Stein

Proceedings of the Design and Analysis of Algorithms, 2012

The Online Metric Matching Problem for Doubling Metrics.

[BibT_eX]

[DOI]

Kevin Lewi

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Robust sensor placements at informative and communication-efficient locations.

[BibT_eX]

[DOI]

ACM Trans. Sens. Networks, 2011

Set connectivity problems in undirected graphs and the directed steiner network problem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2011

Simultaneous Optimization of Sensor Placements and Balanced Schedules.

[BibT_eX]

[DOI]

IEEE Trans. Autom. Control., 2011

Nonclairvoyantly scheduling power-heterogeneous processors.

[BibT_eX]

[DOI]

Sustain. Comput. Informatics Syst., 2011

Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Forest Density Estimation.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2011

Making Doubling Metrics Geodesic.

[BibT_eX]

[DOI]

Algorithmica, 2011

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Welfare and Profit Maximization with Production Costs.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Dial a Ride from k-forest.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

ACM Trans. Algorithms, 2010

An improved approximation algorithm for requirement cut.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2010

A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems.

[BibT_eX]

[DOI]

Math. Oper. Res., 2010

Ultra-low-dimensional embeddings for doubling metrics.

[BibT_eX]

[DOI]

J. ACM, 2010

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

[BibT_eX]

[DOI]

CoRR, 2010

Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms.

[BibT_eX]

[DOI]

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

Scheduling jobs with varying parallelizability to reduce variance.

[BibT_eX]

[DOI]

Sungjin Im

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Tree Embeddings for Two-Edge-Connected Network Design.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Scalably Scheduling Power-Heterogeneous Processors.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

10211 Abstracts Collection - Flexible Network Design.

[BibT_eX]

[DOI]

Proceedings of the Flexible Network Design, 24.05. - 28.05.2010, 2010

Network-wide deployment of intrusion detection and prevention systems.

[BibT_eX]

[DOI]

Vyas Sekar

Michael K. Reiter

Proceedings of the 2010 ACM Conference on Emerging Networking Experiments and Technology, 2010

Coordinated sampling sans Origin-Destination identifiers: Algorithms and analysis.

[BibT_eX]

[DOI]

Proceedings of the Second International Conference on Communication Systems and Networks, 2010

Forest Density Estimation.

[BibT_eX]

[DOI]

Proceedings of the COLT 2010, 2010

2009

Metric Embeddings with Relaxed Guarantees.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Small Hop-diameter Sparse Spanners for Doubling Metrics.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2009

Differentially Private Approximation Algorithms

[BibT_eX]

[DOI]

CoRR, 2009

A constant-factor approximation for stochastic Steiner forest.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Approximate clustering without the approximation.

[BibT_eX]

[DOI]

Maria-Florina Balcan

Avrim Blum

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Secretary problems: weights and discounts.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Simultaneous placement and scheduling of sensors.

[BibT_eX]

[DOI]

Proceedings of the 8th International Conference on Information Processing in Sensor Networks, 2009

Differentially Private Combinatorial Optimization.

[BibT_eX]

[DOI]

Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

Scheduling with Outliers.

[BibT_eX]

[DOI]

Danny Segev

Proceedings of the Approximation, 2009

2008

Extracting Dynamics from Static Cancer Expression Data.

[BibT_eX]

[DOI]

Ziv Bar-Joseph

IEEE ACM Trans. Comput. Biol. Bioinform., 2008

On the approximability of some network design problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.

[BibT_eX]

[DOI]

Shuchi Chawla

Harald Räcke

ACM Trans. Algorithms, 2008

Simpler Analyses of Local Search Algorithms for Facility Location

[BibT_eX]

[DOI]

Kanat Tangwongsan

CoRR, 2008

Cost-Sharing Mechanisms for Network Design.

[BibT_eX]

[DOI]

Aravind Srinivasan

Éva Tardos

Algorithmica, 2008

Stochastic analyses for online combinatorial optimization problems.

[BibT_eX]

[DOI]

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

A plant location guide for the unsure.

[BibT_eX]

[DOI]

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

How to Complete a Doubling Metric.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

All-Norms and All-L_p-Norms Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007

LP Rounding Approximation Algorithms for Stochastic Network Design.

[BibT_eX]

[DOI]

Amitabh Sinha

Math. Oper. Res., 2007

Approximation via cost sharing: Simpler and better approximation algorithms for network design.

[BibT_eX]

[DOI]

J. ACM, 2007

Dial a Ride from k-forest

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

CoRR, 2007

Approximation Algorithms for the Unsplittable Flow Problem.

[BibT_eX]

[DOI]

Algorithmica, 2007

An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.

[BibT_eX]

[DOI]

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

Selecting Observations against Adversarial Objectives.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 20, 2007

Infrastructure Leasing Problems.

[BibT_eX]

[DOI]

Barbara M. Anthony

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Pricing Tree Access Networks with Connected Backbones.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2007

An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2007

On Configuring BGP Route Reflectors.

[BibT_eX]

[DOI]

Proceedings of the Second International Conference on COMmunication System softWAre and MiddlewaRE (COMSWARE 2007), 2007

Stochastic Steiner Tree with Non-uniform Inflation.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Proceedings of the Approximation, 2007

2006

An Improved Approximation Ratio for the Covering Steiner Problem.

[BibT_eX]

[DOI]

Aravind Srinivasan

Theory Comput., 2006

Embedding k-Outerplanar Graphs into l 1.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Approximation Algorithms for Minimizing Average Distortion.

[BibT_eX]

[DOI]

Kedar Dhamdhere

Theory Comput. Syst., 2006

Approximating unique games.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Oblivious network design.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Harald Räcke

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved embeddings of graph metrics into random trees.

[BibT_eX]

[DOI]

Kedar Dhamdhere

Harald Räcke

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Quorum placement in networks: minimizing network congestion.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Near-optimal sensor placements: maximizing information while minimizing communication cost.

[BibT_eX]

[DOI]

Proceedings of the Fifth International Conference on Information Processing in Sensor Networks, 2006

Spanners with Slack.

[BibT_eX]

[DOI]

Michael Dinitz

Proceedings of the Algorithms, 2006

2005

On a bidirected relaxation for the MULTIWAY CUT problem.

[BibT_eX]

[DOI]

Chandra Chekuri

Discret. Appl. Math., 2005

Building Edge-Failure Resilient Networks.

[BibT_eX]

[DOI]

Algorithmica, 2005

Approximation algorithms for low-distortion embeddings into low-dimensional spaces.

[BibT_eX]

[DOI]

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

Quorum placement in networks to minimize access delays.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Stochastic Steiner Trees Without a Root.

[BibT_eX]

[DOI]

Martin Pál

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Metric Embeddings with Relaxed Guarantees.

[BibT_eX]

[DOI]

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

What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

Where's the Winner? Max-Finding and Sorting with Metric Costs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

2004

Traveling with a Pez Dispenser (or, Routing Issues in MPLS).

[BibT_eX]

[DOI]

Rajeev Rastogi

SIAM J. Comput., 2004

Cuts, Trees and l1-Embeddings of Graphs.

[BibT_eX]

[DOI]

Comb., 2004

Boosted sampling: approximation algorithms for stochastic optimization.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.

[BibT_eX]

[DOI]

Amitabh Sinha

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

2003

An elementary proof of a theorem of Johnson and Lindenstrauss.

[BibT_eX]

[DOI]

Sanjoy Dasgupta

Random Struct. Algorithms, 2003

Simpler and better approximation algorithms for network design.

[BibT_eX]

[DOI]

Tim Roughgarden

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Tree based MPLS routing.

[BibT_eX]

[DOI]

Mikkel Thorup

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Counting inversions in lists.

[BibT_eX]

[DOI]

Francis Zane

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Improved results for directed multicut.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Embedding k-outerplanar graphs into l1.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Lower bounds for embedding edit distance into normed spaces.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Exploring the trade-off between label size and stack depth in MPLS Routing.

[BibT_eX]

[DOI]

Rajeev Rastogi

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

On the Covering Steiner Problem.

[BibT_eX]

[DOI]

Aravind Srinivasan

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.

[BibT_eX]

[DOI]