# Anupam Gupta

According to our database

Collaborative distances:

^{1}, Anupam Gupta authored at least 192 papers between 2000 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2020

Neutralizing Self-Selection Bias in Sampling for Sortition.

CoRR, 2020

Caching with Time Windows and Delays.

CoRR, 2020

Dimension-Free Bounds on Chasing Convex Functions.

CoRR, 2020

Optimal Bounds for the k-cut Problem.

CoRR, 2020

Random-Order Models.

CoRR, 2020

Stochastic Makespan Minimization in Structured Set Systems.

CoRR, 2020

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

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

Caching with time windows.

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

The Online Submodular Cover Problem.

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

Chasing Convex Bodies with Linear Competitive Ratio.

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

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

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Robust Algorithms for the Secretary Problem.

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

2019

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

SIAM J. Discret. Math., 2019

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

SIAM J. Comput., 2019

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

CoRR, 2019

Spatiotemporal Filtering for Event-Based Action Recognition.

CoRR, 2019

The number of minimum

*k*-cuts: improving the Karger-Stein bound.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Losing Treewidth by Separating Subsets.

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

Elastic Caching.

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

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

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

A Nearly-Linear Bound for Chasing Nested Convex Bodies.

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

The Markovian Price of Information.

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

Stochastic Online Metric Matching.

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

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

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

Non-Clairvoyant Precedence Constrained Scheduling.

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

Better Algorithms for Stochastic Bandits with Adversarial Corruptions.

Proceedings of the Conference on Learning Theory, 2019

2018

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

SIAM J. Comput., 2018

Metric embedding via shortest path decompositions.

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

An FPT Algorithm Beating 2-Approximation for

*k*-Cut.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Stochastic Load Balancing on Unrelated Machines.

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

A Local-Search Algorithm for Steiner Forest.

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

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

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

Non-Preemptive Flow-Time Minimization via Rejections.

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

Fully-Dynamic Bin Packing with Little Repacking.

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

Faster Exact and Approximate Algorithms for k-Cut.

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

Interactively Modeling and Visualizing Neighborhood Accessibility at Scale: An Initial Study of Washington DC.

Proceedings of the 20th International ACM SIGACCESS Conference on Computers and Accessibility, 2018

2017

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.

Math. Oper. Res., 2017

Potential-Function Proofs for First-Order Methods.

CoRR, 2017

Fully-Dynamic Bin Packing with Limited Repacking.

CoRR, 2017

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

CoRR, 2017

Online and dynamic algorithms for set cover.

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

Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions.

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

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

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

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration.

Proceedings of the 30th Conference on Learning Theory, 2017

Stochastic Unsplittable Flows.

Proceedings of the Approximation, 2017

2016

Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets.

ACM Trans. Algorithms, 2016

On Hierarchical Routing in Doubling Metrics.

ACM Trans. Algorithms, 2016

Algorithms for Hub Label Optimization.

ACM Trans. Algorithms, 2016

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

SIAM J. Comput., 2016

How the Experts Algorithm Can Help Solve LPs Online.

Math. Oper. Res., 2016

An Improved Integrality Gap for Asymmetric TSP Paths.

Math. Oper. Res., 2016

Algorithms and Adaptivity Gaps for Stochastic Probing.

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

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

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

Online Algorithms for Covering and Packing Problems with Convex Objectives.

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

Pure Exploration of Multi-armed Bandit Under Matroid Constraints.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Running Errands in Time: Approximation Algorithms for Stochastic Orienteering.

Math. Oper. Res., 2015

Hybrid Lattice Boltzmann/Finite Difference simulations of viscoelastic multicomponent flows in confined geometries.

J. Comput. Phys., 2015

Greedy Algorithms for Steiner Forest.

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.

Proceedings of the Approximation, 2015

2014

Vertex Sparsifiers: New Results from Old Techniques.

SIAM J. Comput., 2014

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

Theory Comput. Syst., 2014

Thresholded covering algorithms for robust and max-min optimization.

Math. Program., 2014

Approximating Sparse Covering Integer Programs Online.

Math. Oper. Res., 2014

Online Packing and Covering Framework with Convex Objectives.

CoRR, 2014

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

Algorithmica, 2014

Minimum

*d*-dimensional arrangement with fixed points.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Maintaining Assignments Online: Matching, Scheduling, and Flows.

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

Online Steiner Tree with Deletions.

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

Towards (1 +

*∊*)-Approximate Flow Sparsifiers.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Changing Bases: Multistage Optimization for Matroids and Matchings.

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

How Experts Can Solve LPs Online.

Proceedings of the Algorithms - ESA 2014, 2014

Novel approach for security in Wireless Sensor Network using bio-inspirations.

Proceedings of the Sixth International Conference on Communication Systems and Networks, 2014

2013

Privately Releasing Conjunctions and the Statistical Query Barrier.

SIAM J. Comput., 2013

Set Covering with Our Eyes Closed.

SIAM J. Comput., 2013

Clustering under approximation stability.

J. ACM, 2013

Some Efficient Solutions to Yao's Millionaire Problem.

CoRR, 2013

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

CoRR, 2013

Minimum d-dimensional arrangement with fixed points.

CoRR, 2013

Towards (1+ε)-Approximate Flow Sparsifiers.

CoRR, 2013

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

Proceedings of the Symposium on Theory of Computing Conference, 2013

Harnessing the power of two crossmatches.

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Thrifty Algorithms for Multistage Robust Optimization.

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

A Stochastic Probing Problem with Applications.

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Packing Interdiction and Partial Covering Problems.

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

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

Proceedings of the Innovations in Theoretical Computer Science, 2013

The Approximability of the Binary Paintshop Problem.

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

2012

Online and Stochastic Survivable Network Design.

SIAM J. Comput., 2012

Approximating TSP on Metrics with Bounded Global Growth.

SIAM J. Comput., 2012

Technical Note - Approximation Algorithms for VRP with Stochastic Demands.

Oper. Res., 2012

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

Algorithmica, 2012

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

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

Iterative Constructions and Private Data Release.

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

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

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

Approximation algorithms for stochastic orienteering.

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

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

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

Multicast Routing for Energy Minimization Using Speed Scaling.

Proceedings of the Design and Analysis of Algorithms, 2012

The Online Metric Matching Problem for Doubling Metrics.

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

Cancer data investigation using variable precision Rough set with flexible classification.

Proceedings of the Second International Conference on Computational Science, 2012

2011

Robust sensor placements at informative and communication-efficient locations.

ACM Trans. Sens. Networks, 2011

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

ACM Trans. Algorithms, 2011

Simultaneous Optimization of Sensor Placements and Balanced Schedules.

IEEE Trans. Autom. Control., 2011

Nonclairvoyantly scheduling power-heterogeneous processors.

Sustain. Comput. Informatics Syst., 2011

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

SIAM J. Comput., 2011

Forest Density Estimation.

J. Mach. Learn. Res., 2011

Making Doubling Metrics Geodesic.

Algorithmica, 2011

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

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.

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

Welfare and Profit Maximization with Production Costs.

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

2010

Dial a Ride from

*k*-forest.
ACM Trans. Algorithms, 2010

An improved approximation algorithm for requirement cut.

Oper. Res. Lett., 2010

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

Math. Oper. Res., 2010

Ultra-low-dimensional embeddings for doubling metrics.

J. ACM, 2010

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

CoRR, 2010

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

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

Scheduling jobs with varying parallelizability to reduce variance.

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.

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

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

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

Scalably Scheduling Power-Heterogeneous Processors.

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).

Proceedings of the Algorithms, 2010

10211 Abstracts Collection - Flexible Network Design.

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

Network-wide deployment of intrusion detection and prevention systems.

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

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

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

Forest Density Estimation.

Proceedings of the COLT 2010, 2010

2009

Metric Embeddings with Relaxed Guarantees.

SIAM J. Comput., 2009

Small Hop-diameter Sparse Spanners for Doubling Metrics.

Discret. Comput. Geom., 2009

Differentially Private Approximation Algorithms

CoRR, 2009

A constant-factor approximation for stochastic Steiner forest.

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

Approximate clustering without the approximation.

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

Secretary problems: weights and discounts.

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

Simultaneous placement and scheduling of sensors.

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

Differentially Private Combinatorial Optimization.

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

Scheduling with Outliers.

Proceedings of the Approximation, 2009

2008

Extracting Dynamics from Static Cancer Expression Data.

IEEE/ACM Trans. Comput. Biology Bioinform., 2008

On the approximability of some network design problems.

ACM Trans. Algorithms, 2008

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

ACM Trans. Algorithms, 2008

Simpler Analyses of Local Search Algorithms for Facility Location

CoRR, 2008

Cost-Sharing Mechanisms for Network Design.

Algorithmica, 2008

Stochastic analyses for online combinatorial optimization problems.

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

A plant location guide for the unsure.

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

How to Complete a Doubling Metric.

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

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

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.

Math. Oper. Res., 2007

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

J. ACM, 2007

Dial a Ride from k-forest

CoRR, 2007

Approximation Algorithms for the Unsplittable Flow Problem.

Algorithmica, 2007

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

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

Selecting Observations against Adversarial Objectives.

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

Infrastructure Leasing Problems.

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Pricing Tree Access Networks with Connected Backbones.

Proceedings of the Algorithms, 2007

Proceedings of the Algorithms, 2007

On Configuring BGP Route Reflectors.

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

Stochastic Steiner Tree with Non-uniform Inflation.

Proceedings of the Approximation, 2007

2006

An Improved Approximation Ratio for the Covering Steiner Problem.

Theory Comput., 2006

SIAM J. Discret. Math., 2006

Approximation Algorithms for Minimizing Average Distortion.

Theory Comput. Syst., 2006

Approximating unique games.

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

Oblivious network design.

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

Improved embeddings of graph metrics into random trees.

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

Quorum placement in networks: minimizing network congestion.

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

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

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

Spanners with Slack.

Proceedings of the Algorithms, 2006

2005

On a bidirected relaxation for the MULTIWAY CUT problem.

Discret. Appl. Math., 2005

Building Edge-Failure Resilient Networks.

Algorithmica, 2005

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

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

Quorum placement in networks to minimize access delays.

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

Stochastic Steiner Trees Without a Root.

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

Metric Embeddings with Relaxed Guarantees.

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

What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.

Proceedings of the Approximation, 2005

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

Proceedings of the Approximation, 2005

2004

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

SIAM J. Comput., 2004

Cuts, Trees and l

_{1}-Embeddings of Graphs.
Combinatorica, 2004

Boosted sampling: approximation algorithms for stochastic optimization.

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.

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

2003

An elementary proof of a theorem of Johnson and Lindenstrauss.

Random Struct. Algorithms, 2003

Simpler and better approximation algorithms for network design.

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

Tree based MPLS routing.

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

Counting inversions in lists.

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

Improved results for directed multicut.

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

Embedding k-outerplanar graphs into l1.

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

Lower bounds for embedding edit distance into normed spaces.

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.

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.

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.

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Bounded Geometries, Fractals, and Low-Distortion Embeddings.

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

A Constant-Factor Approximation Algorithm for the Multicommodity.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Improved Bandwidth Approximation for Trees and Chordal Graphs.

J. Algorithms, 2001

Provisioning a virtual private network: a network design problem for multicommodity flow.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Steiner points in tree metrics don't (really) help.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Sorting and Selection with Structured Costs.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Embedding Tree Metrics into Low-Dimensional Euclidean Spaces.

Discret. Comput. Geom., 2000

A constant factor approximation algorithm for a class of classification problems.

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Improved bandwidth approximation for trees.

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000