Chandra Chekuri

According to our database1, Chandra Chekuri authored at least 132 papers between 1995 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

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
Minimum Cuts and Sparsification in Hypergraphs.
SIAM J. Comput., 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
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

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

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

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. Discrete Math., 2014

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

Polynomial bounds for the grid-minor theorem.
Proceedings of the Symposium on Theory of Computing, 2014

The All-or-Nothing Flow Problem in Directed Graphs with Symmetric Demand Pairs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Centrality of Trees for Capacitated k-Center.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

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

Approximation Algorithms for Euler Genus and Related Problems.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

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

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

Multicommodity flows and cuts in polymatroidal networks.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Prize-Collecting Survivable Network Design in Node-Weighted Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

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

Submodular function maximization via the multilinear relaxation and contention resolution schemes.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 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

Approximability of Capacitated Network Design.
Proceedings of the Integer Programming and Combinatoral Optimization, 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

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

Flow-Cut Gaps for Integer and Fractional Multiflows.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

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

2009
Disjoint bases in a polymatroid.
Random Struct. Algorithms, 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. Discrete Math., 2008

Improved algorithms for orienteering and related problems.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Set connectivity problems in undirected graphs and the directed Steiner network problem.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Pruning 2-Connected Graphs.
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 of Computing, 2007

Multicommodity demand flow in a tree and packing integer programs.
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

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

Buy-at-Bulk Network Design with Protection.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

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

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

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

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

A greedy approximation algorithm for the group Steiner problem.
Discrete Applied Mathematics, 2006

Design tools for transparent optical networks.
Bell Labs Technical Journal, 2006

Edge-disjoint paths in Planar graphs with constant congestion.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Non-cooperative multicast and facility location games.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 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

On a bidirected relaxation for the MULTIWAY CUT problem.
Discrete Applied Mathematics, 2005

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

On average throughput and alphabet size in network coding.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 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. Discrete Math., 2004

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

The all-or-nothing multicommodity flow problem.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 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
Edge disjoint paths revisited.
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

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

2002
Approximation schemes for preemptive weighted flow time.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Building Edge-Failure Resilient Networks.
Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks.
Proceedings of the 10th IEEE International Conference on Network Protocols (ICNP 2002), 2002

Approximation Algorithms for the Unsplittable Flow Problem.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

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

Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine.
Discrete Applied Mathematics, 1999

Performance Guarantees for the TSP with a Parameterized Triangle Inequality.
Proceedings of the Algorithms and Data Structures, 6th International Workshop, 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

Approximation Algorithms for Directed Steiner Problems.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines.
Proceedings of the Integer Programming and Combinatorial Optimization, 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
Incremental Clustering and Dynamic Information Retrieval.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Approximation Techniques for Average Completion Time Scheduling.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

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

Conjunctive Query Containment Revisited.
Proceedings of the Database Theory, 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


  Loading...