# Chandra Chekuri

According to our database1, Chandra Chekuri authored at least 142 papers between 1995 and 2020.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
Fast LP-based Approximations for Geometric Packing and Covering Problems.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Algorithms for Intersection Graphs of Multiple Intervals and Pseudo Disks.
CoRR, 2019

On Approximating Partial Set Cover and Generalizations.
CoRR, 2019

$\ell_1$-sparsity Approximation Bounds for Packing Integer Programs.
CoRR, 2019

Parallelizing greedy for submodular set function maximization in matroids and beyond.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Approximating (Sparse) Covering Integer Programs.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Submodular Function Maximization in Parallel via the Multilinear Relaxation.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

LP Relaxation and Tree Packing for Minimum k-cuts.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

\ell _1 -sparsity Approximation Bounds for Packing Integer Programs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs.
SIAM J. Discret. Math., 2018

Approximation Algorithms for Euler Genus and Related Problems.
SIAM J. Comput., 2018

Minimum Cuts and Sparsification in Hypergraphs.
SIAM J. Comput., 2018

Fast Approximations for Metric-TSP via Linear Programming.
CoRR, 2018

A Note on Iterated Rounding for the Survivable Network Design Problem.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Randomized MWU for Positive LPs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Congestion Minimization for Multipath Routing via Multiroute Flows.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations.
Proceedings of the Approximation, 2018

2017
A note on approximate strengths of edges in a hypergraph.
CoRR, 2017

Computing minimum cuts in hypergraphs.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating Multicut and the Demand Graph.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Graph Coloring.
Encyclopedia of Algorithms, 2016

Multicommodity Flow, Well-linked Terminals and Routing Problems.
Encyclopedia of Algorithms, 2016

Polynomial Bounds for the Grid-Minor Theorem.
J. ACM, 2016

A note on the Survivable Network Design Problem.
CoRR, 2016

A Fast Approximation for Maximum Weight Matroid Intersection.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
Multicommodity Flows and Cuts in Polymatroidal Networks.
SIAM J. Comput., 2015

The all-or-nothing flow problem in directed graphs with symmetric demand pairs.
Math. Program., 2015

Centrality of trees for capacitated k-center.
Math. Program., 2015

Approximability of Capacitated Network Design.
Algorithmica, 2015

Degree-3 Treewidth Sparsifiers.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Delay-constrained unicast and the triangle-cast problem.
Proceedings of the IEEE International Symposium on Information Theory, 2015

On Multiplicative Weight Updates for Concave and Submodular Function Maximization.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Streaming Algorithms for Submodular Function Maximization.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On Element-Connectivity Preserving Graph Simplification.
Proceedings of the Algorithms - ESA 2015, 2015

2014
A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests.
SIAM J. Discret. Math., 2014

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.
SIAM J. Comput., 2014

2013
The All-or-Nothing Multicommodity Flow Problem.
SIAM J. Comput., 2013

Flow-cut gaps for integer and fractional multiflows.
J. Comb. Theory, Ser. B, 2013

Large-treewidth graph decompositions and applications.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Maximum Edge-Disjoint Paths in k-Sums of Graphs.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor.
Theory Comput., 2012

Improved algorithms for orienteering and related problems.
ACM Trans. Algorithms, 2012

On the set multicover problem in geometric settings.
ACM Trans. Algorithms, 2012

Pruning 2-Connected Graphs.
Algorithmica, 2012

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

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

2011
Set connectivity problems in undirected graphs and the directed steiner network problem.
ACM Trans. Algorithms, 2011

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.
SIAM J. Comput., 2011

Math. Oper. Res., 2011

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Prize-collecting Steiner Problems on Planar Graphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Submodular Cost Allocation Problem and Applications.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Approximation Algorithms for Submodular Multiway Partition.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design.
SIAM J. Comput., 2010

Prize-Collecting Steiner Tree and Forest in Planar Graphs
CoRR, 2010

New Models and Algorithms for Throughput Maximization in Broadcast Scheduling - (Extended Abstract).
Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Edge-Disjoint Paths in Planar Graphs with Constant Congestion.
SIAM J. Comput., 2009

Disjoint bases in a polymatroid.
Random Struct. Algorithms, 2009

Randomized Pipage Rounding for Matroid Polytopes and Applications
CoRR, 2009

Longest Wait First for Broadcast Scheduling
CoRR, 2009

Foreword.
Algorithmica, 2009

A Note on Multiflows and Treewidth.
Algorithmica, 2009

Longest Wait First for Broadcast Scheduling [Extended Abstract].
Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Online scheduling to minimize the maximum delay factor.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Topology Formation for Wireless Mesh Network Planning.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009

A Graph Reduction Step Preserving Element-Connectivity and Applications.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling.
Proceedings of the Algorithms, 2009

On the set multi-cover problem in geometric settings.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Truthful Mechanisms via Greedy Iterative Packing.
Proceedings of the Approximation, 2009

Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs.
Proceedings of the Approximation, 2009

2008
Multicommodity Flow, Well-linked Terminals and Routing Problems.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Approximate Integer Decompositions for Undirected Network Design Problems.
SIAM J. Discret. Math., 2008

Min-Cost 2-Connected Subgraphs With k Terminals
CoRR, 2008

Algorithms for 2-Route Cut Problems.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Single-Sink Network Design with Vertex Connectivity Requirements.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem.
Theory Comput., 2007

Multicommodity demand flow in a tree and packing integer programs.
ACM Trans. Algorithms, 2007

Edge-disjoint paths revisited.
ACM Trans. Algorithms, 2007

Routing and network design with robustness to changing or uncertain traffic demands.
SIGACT News, 2007

Hardness of robust network design.
Networks, 2007

Non-Cooperative Multicast and Facility Location Games.
IEEE J. Sel. Areas Commun., 2007

Approximation Algorithms for Orienteering with Time Windows
CoRR, 2007

Approximation Algorithms for the Unsplittable Flow Problem.
Algorithmica, 2007

Approximation algorithms for node-weighted buy-at-bulk network design.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).
Proceedings of the Integer Programming and Combinatorial Optimization, 2007

2006
An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow.
Theory Comput., 2006

On average throughput and alphabet size in network coding.
IEEE Trans. Inf. Theory, 2006

Embedding k-Outerplanar Graphs into l 1.
SIAM J. Discret. Math., 2006

The Steiner k-Cut Problem.
SIAM J. Discret. Math., 2006

Special Issue: FOCS 2003.
J. Comput. Syst. Sci., 2006

A greedy approximation algorithm for the group Steiner problem.
Discret. Appl. Math., 2006

Design tools for transparent optical networks.
Bell Labs Tech. J., 2006

On Achievable Information Rates in Single-Source Non-Uniform Demand Networks.
Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem.
Proceedings of the Approximation, 2006

2005
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem.
SIAM J. Comput., 2005

Routing bandwidth guaranteed paths with local restoration in label switched networks.
IEEE J. Sel. Areas Commun., 2005

On a bidirected relaxation for the MULTIWAY CUT problem.
Discret. Appl. Math., 2005

Building Edge-Failure Resilient Networks.
Algorithmica, 2005

Multicommodity flow, well-linked terminals, and routing problems.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

A Recursive Greedy Algorithm for Walks in Directed Graphs.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Sampling Bounds for Stochastic Optimization.
Proceedings of the Approximation, 2005

2004
Approximation Algorithms for Minimizing AverageWeighted Completion Time.
Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.
SIAM J. Discret. Math., 2004

On Multidimensional Packing Problems.
SIAM J. Comput., 2004

Incremental Clustering and Dynamic Information Retrieval.
SIAM J. Comput., 2004

Multi-processor scheduling to minimize flow time with epsilon resource augmentation.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Edge-Disjoint Paths in Planar Graphs.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Maximum Coverage Problem with Group Budget Constraints and Applications.
Proceedings of the Approximation, 2004

2003
Embedding k-outerplanar graphs into l1.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Multicommodity Demand Flow in a Tree.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Approximating Steiner k-Cuts.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2001
Approximation Techniques for Average Completion Time Scheduling.
SIAM J. Comput., 2001

An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines.
J. Algorithms, 2001

Approximation Schemes for Preemptive Weighted Flow Time
Electronic Colloquium on Computational Complexity (ECCC), 2001

Algorithms for minimizing weighted flow time.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Approximation algorithms for the metric labeling problem via a new linear programming formulation.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A deterministic algorithm for the cost-distance problem.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000
Conjunctive query containment revisited.
Theor. Comput. Sci., 2000

Performance guarantees for the TSP with a parameterized triangle inequality.
Inf. Process. Lett., 2000

A PTAS for the multiple knapsack problem.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Blocking probability estimates in a partitioned sector TDMA system.
Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2000), 2000

1999
Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).
SIAM J. Comput., 1999

Approximation Algorithms for Directed Steiner Problems.
J. Algorithms, 1999

Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine.
Discret. Appl. Math., 1999

Minimizing Weighted Completion Time on a Single Machine.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On Multi-Dimensional Packing Problems.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Filtering with Approximate Predicates.
Proceedings of the VLDB'98, 1998

Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Approximating a Finite Metric by a Small Number of Tree Metrics.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Experimental Study of Minimum Cut Algorithms.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Profile-driven Instruction Level Parallel Scheduling with Application to Super Blocks.
Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, 1996

1995
Scheduling Problems in Parallel Query Optimization.
Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1995