Chandra Chekuri

Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel: Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory, Ser. B 103(2): 248-273 (2013)

Chandra Chekuri, Alina Ene: Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion. SODA 2013: 326-341

Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd: Maximum Edge-Disjoint Paths in $k$-sums of Graphs. CoRR abs/1303.4897 (2013)

Chandra Chekuri, Julia Chuzhoy: Large-Treewidth Graph Decompositions and Applications. CoRR abs/1304.1577 (2013)

Chandra Chekuri, Anastasios Sidiropoulos: Approximation algorithms for Euler genus and related problems. CoRR abs/1304.2416 (2013)

Chandra Chekuri, Nitish Korula: Pruning 2-Connected Graphs. Algorithmica 62(1-2): 436-463 (2012)

Chandra Chekuri, Nitish Korula, Martin Pál: Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms 8(3): 23 (2012)

Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled: On the set multicover problem in geometric settings. ACM Transactions on Algorithms 9(1): 9 (2012)

Chandra Chekuri, Sungjin Im, Benjamin Moseley: Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor. Theory of Computing 8(1): 165-195 (2012)

Chandra Chekuri, Alina Ene, Ali Vakilian: Prize-Collecting Survivable Network Design in Node-Weighted Graphs. APPROX-RANDOM 2012: 98-109

Chandra Chekuri, Alina Ene, Ali Vakilian: Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs. ICALP (1) 2012: 206-217

Chandra Chekuri, Sreeram Kannan, Adnan Raja, Pramod Viswanath: Multicommodity flows and cuts in polymatroidal networks. ITCS 2012: 399-408

Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang: Buy-at-Bulk Network Design with Protection. Math. Oper. Res. 36(1): 71-87 (2011)

Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint. SIAM J. Comput. 40(6): 1740-1766 (2011)

Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev: Set connectivity problems in undirected graphs and the directed steiner network problem. ACM Transactions on Algorithms 7(2): 18 (2011)

Chandra Chekuri, Alina Ene: Approximation Algorithms for Submodular Multiway Partition. FOCS 2011: 807-816

Chandra Chekuri, Alina Ene: Submodular Cost Allocation Problem and Applications. ICALP (1) 2011: 354-366

Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula: Approximability of Capacitated Network Design. IPCO 2011: 78-91

MohammadHossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, Dániel Marx: Prize-collecting Steiner Problems on Planar Graphs. SODA 2011: 1028-1049

Chandra Chekuri, Jan Vondrák, Rico Zenklusen: Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. SODA 2011: 1080-1097

Jan Vondrák, Chandra Chekuri, Rico Zenklusen: Submodular function maximization via the multilinear relaxation and contention resolution schemes. STOC 2011: 783-792

Chandra Chekuri, Alina Ene: Submodular Cost Allocation Problem and Applications. CoRR abs/1105.2040 (2011)

Chandra Chekuri, Alina Ene: Approximation Algorithms for Submodular Multiway Partition. CoRR abs/1105.2048 (2011)

Chandra Chekuri, Jan Vondrák, Rico Zenklusen: Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. CoRR abs/1105.4593 (2011)

Chandra Chekuri, Sreeram Kannan, Adnan Raja, Pramod Viswanath: Multicommodity Flows and Cuts in Polymatroidal Networks. CoRR abs/1110.6832 (2011)

Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design. SIAM J. Comput. 39(5): 1772-1798 (2010)

Chandra Chekuri, Jan Vondrák, Rico Zenklusen: Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. FOCS 2010: 575-584

Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel: Flow-Cut Gaps for Integer and Fractional Multiflows. SODA 2010: 1198-1208

Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard Matthew McCutchen, Benjamin Moseley, Louiqa Raschid: New Models and Algorithms for Throughput Maximization in Broadcast Scheduling - (Extended Abstract). WAOA 2010: 71-82

Chandra Chekuri, Alina Ene, Nitish Korula: Prize-Collecting Steiner Tree and Forest in Planar Graphs. CoRR abs/1006.4357 (2010)

Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel: Flow-Cut Gaps for Integer and Fractional Multiflows. CoRR abs/1008.2136 (2010)

Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula: Approximability of Capacitated Network Design. CoRR abs/1009.5734 (2010)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: A Note on Multiflows and Treewidth. Algorithmica 54(3): 400-412 (2009)

Chandra Chekuri, Luca Trevisan: Foreword. Algorithmica 55(1): 111-112 (2009)

Gruia Calinescu, Chandra Chekuri, Jan Vondrák: Disjoint bases in a polymatroid. Random Struct. Algorithms 35(4): 418-430 (2009)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-Disjoint Paths in Planar Graphs with Constant Congestion. SIAM J. Comput. 39(1): 281-301 (2009)

Chandra Chekuri, Alina Ene, Nitish Korula: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. APPROX-RANDOM 2009: 42-55

Chandra Chekuri, Iftah Gamzu: Truthful Mechanisms via Greedy Iterative Packing. APPROX-RANDOM 2009: 56-69

Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled: On the set multi-cover problem in geometric settings. Symposium on Computational Geometry 2009: 341-350

Chandra Chekuri, Sungjin Im, Benjamin Moseley: Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. ESA 2009: 444-455

Chandra Chekuri, Nitish Korula: A Graph Reduction Step Preserving Element-Connectivity and Applications. ICALP (1) 2009: 254-265

Chun-cheng Chen, Chandra Chekuri, D. Klabjan: Topology Formation for Wireless Mesh Network Planning. INFOCOM 2009: 2671-2675

Chandra Chekuri, Benjamin Moseley: Online scheduling to minimize the maximum delay factor. SODA 2009: 1116-1125

Chandra Chekuri, Sungjin Im, Benjamin Moseley: Longest Wait First for Broadcast Scheduling [Extended Abstract]. WAOA 2009: 62-74

Chandra Chekuri, Nitish Korula: A Graph Reduction Step Preserving Element-Connectivity and Applications. CoRR abs/0902.2795 (2009)

Chandra Chekuri, Sungjin Im, Benjamin Moseley: Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. CoRR abs/0906.2048 (2009)

Chandra Chekuri, Sungjin Im, Benjamin Moseley: Longest Wait First for Broadcast Scheduling. CoRR abs/0906.2395 (2009)

Chandra Chekuri, Iftah Gamzu: Truthful Mechanisms via Greedy Iterative Packing. CoRR abs/0906.2466 (2009)

Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled: On the Set Multi-Cover Problem in Geometric Settings. CoRR abs/0909.0537 (2009)

Chandra Chekuri, Jan Vondrák: Randomized Pipage Rounding for Matroid Polytopes and Applications. CoRR abs/0909.4348 (2009)

Chandra Chekuri, F. Bruce Shepherd: Approximate Integer Decompositions for Undirected Network Design Problems. SIAM J. Discrete Math. 23(1): 163-177 (2008)

Chandra Chekuri, Nitish Korula: Pruning 2-Connected Graphs. FSTTCS 2008: 119-130

Chandra Chekuri, Nitish Korula: Single-Sink Network Design with Vertex Connectivity Requirements. FSTTCS 2008: 131-142

Chandra Chekuri, Sanjeev Khanna: Algorithms for 2-Route Cut Problems. ICALP (1) 2008: 472-484

Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev: Set connectivity problems in undirected graphs and the directed Steiner network problem. SODA 2008: 532-541

Chandra Chekuri, Nitish Korula, Martin Pál: Improved algorithms for orienteering and related problems. SODA 2008: 661-670

Chandra Chekuri: Multicommodity Flow, Well-linked Terminals and Routing Problems. Encyclopedia of Algorithms 2008

Chandra Chekuri, Nitish Korula: Min-Cost 2-Connected Subgraphs With k Terminals. CoRR abs/0802.2528 (2008)

Chandra Chekuri, Benjamin Moseley: Online Scheduling to Minimize the Maximum Delay Factor. CoRR abs/0807.1891 (2008)

Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar: Approximation Algorithms for the Unsplittable Flow Problem. Algorithmica 47(1): 53-78 (2007)

Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Non-Cooperative Multicast and Facility Location Games. IEEE Journal on Selected Areas in Communications 25(6): 1193-1206 (2007)

Chandra Chekuri, F. Bruce Shepherd, Gianpaolo Oriolo, Maria Grazia Scutellà: Hardness of robust network design. Networks 50(1): 50-54 (2007)

Chandra Chekuri: Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News 38(3): 106-129 (2007)

Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd: Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms 3(3) (2007)

Chandra Chekuri, Sanjeev Khanna: Edge-disjoint paths revisited. ACM Transactions on Algorithms 3(4) (2007)

Chandra Chekuri, Martin Pál: An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. Theory of Computing 3(1): 197-209 (2007)

Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang: Buy-at-Bulk Network Design with Protection. FOCS 2007: 634-644

Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák: Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract). IPCO 2007: 182-196

Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation algorithms for node-weighted buy-at-bulk network design. SODA 2007: 1265-1274

Chandra Chekuri, Nitish Korula: Approximation Algorithms for Orienteering with Time Windows. CoRR abs/0711.4825 (2007)

Chandra Chekuri, Paul Claisse, René-Jean Essiambre, Steven Fortune, Daniel C. Kilper, Wonsuck Lee, Nachi K. Nithi, Iraj Saniee, F. Bruce Shepherd, Christopher A. White, Gordon T. Wilfong, Lisa Zhang: Design tools for transparent optical networks. Bell Labs Technical Journal 11(2): 129-143 (2006)

Chandra Chekuri, Guy Even, Guy Kortsarz: A greedy approximation algorithm for the group Steiner problem. Discrete Applied Mathematics 154(1): 15-34 (2006)

Chandra Chekuri, Daniele Micciancio: Special Issue: FOCS 2003. J. Comput. Syst. Sci. 72(2): 205 (2006)

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-Outerplanar Graphs into l ₁. SIAM J. Discrete Math. 20(1): 119-136 (2006)

Chandra Chekuri, Sudipto Guha, Joseph Naor: The Steiner k-Cut Problem. SIAM J. Discrete Math. 20(1): 261-271 (2006)

Chandra Chekuri, Christina Fragouli, Emina Soljanin: On average throughput and alphabet size in network coding. IEEE Transactions on Information Theory 52(6): 2410-2424 (2006)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Theory of Computing 2(1): 137-146 (2006)

Chandra Chekuri, Martin Pál: An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. APPROX-RANDOM 2006: 95-103

Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. FOCS 2006: 677-686

Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda: Non-cooperative multicast and facility location games. ACM Conference on Electronic Commerce 2006: 72-81

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-disjoint paths in Planar graphs with constant congestion. STOC 2006: 757-766

Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, Danny Raz: Building Edge-Failure Resilient Networks. Algorithmica 43(1-2): 17-41 (2005)

Chandra Chekuri, Anupam Gupta, Amit Kumar: On a bidirected relaxation for the MULTIWAY CUT problem. Discrete Applied Mathematics 150(1-3): 67-79 (2005)

Li Li, Milind M. Buddhikot, Chandra Chekuri, Katherine Guo: Routing bandwidth guaranteed paths with local restoration in label switched networks. IEEE Journal on Selected Areas in Communications 23(2): 437-449 (2005)

Chandra Chekuri, Sanjeev Khanna: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM J. Comput. 35(3): 713-728 (2005)

Moses Charikar, Chandra Chekuri, Martin Pál: Sampling Bounds for Stochastic Optimization. APPROX-RANDOM 2005: 257-269

Chandra Chekuri, Martin Pál: A Recursive Greedy Algorithm for Walks in Directed Graphs. FOCS 2005: 245-253

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. STOC 2005: 183-192

Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan (Eds.): Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings. Lecture Notes in Computer Science 3624, Springer 2005, isbn 3-540-28239-4

Chandra Chekuri, Sanjeev Khanna: On Multidimensional Packing Problems. SIAM J. Comput. 33(4): 837-851 (2004)

Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani: Incremental Clustering and Dynamic Information Retrieval. SIAM J. Comput. 33(6): 1417-1440 (2004)

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J. Discrete Math. 18(3): 608-625 (2004)

Chandra Chekuri, Amit Kumar: Maximum Coverage Problem with Group Budget Constraints and Applications. APPROX-RANDOM 2004: 72-83

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-Disjoint Paths in Planar Graphs. FOCS 2004: 71-80

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: The all-or-nothing multicommodity flow problem. STOC 2004: 156-165

Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar: Multi-processor scheduling to minimize flow time with epsilon resource augmentation. STOC 2004: 363-372

Chandra Chekuri, Sudipto Guha, Joseph Naor: Approximating Steiner k-Cuts. ICALP 2003: 189-199

Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd: Multicommodity Demand Flow in a Tree. ICALP 2003: 410-425

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-outerplanar graphs into l1. SODA 2003: 527-536

Chandra Chekuri, Sanjeev Khanna: Edge disjoint paths revisited. SODA 2003: 628-637

Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar: Approximation Algorithms for the Unsplittable Flow Problem. APPROX 2002: 51-66

Erran L. Li, Milind M. Buddhikot, Chandra Chekuri, Katherine Guo: Routing Bandwidth Guaranteed Paths with Local Restoration in Label Switched Networks. ICNP 2002: 110-121

Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, Danny Raz: Building Edge-Failure Resilient Networks. IPCO 2002: 439-456

Chandra Chekuri, Sanjeev Khanna: Approximation schemes for preemptive weighted flow time. STOC 2002: 297-305

Chandra Chekuri, Michael A. Bender: An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines. J. Algorithms 41(2): 212-224 (2001)

Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein: Approximation Techniques for Average Completion Time Scheduling. SIAM J. Comput. 31(1): 146-166 (2001)

Chandra Chekuri, Sanjeev Khanna: A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. ICALP 2001: 848-861

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: Approximation algorithms for the metric labeling problem via a new linear programming formulation. SODA 2001: 109-118

Chandra Chekuri, Sanjeev Khanna, Joseph Naor: A deterministic algorithm for the cost-distance problem. SODA 2001: 232-233

Chandra Chekuri, Sanjeev Khanna, An Zhu: Algorithms for minimizing weighted flow time. STOC 2001: 84-93

Chandra Chekuri, Sanjeev Khanna: Approximation Schemes for Preemptive Weighted Flow Time. Electronic Colloquium on Computational Complexity (ECCC) 8(065) (2001)

Michael A. Bender, Chandra Chekuri: Performance guarantees for the TSP with a parameterized triangle inequality. Inf. Process. Lett. 73(1-2): 17-21 (2000)

Chandra Chekuri, Anand Rajaraman: Conjunctive query containment revisited. Theor. Comput. Sci. 239(2): 211-229 (2000)

Chandra Chekuri, Kavita Ramanan, Philip A. Whiting, Lisa Zhang: Blocking probability estimates in a partitioned sector TDMA system. DIAL-M 2000: 28-34

Chandra Chekuri, Sanjeev Khanna: A PTAS for the multiple knapsack problem. SODA 2000: 213-222

Chandra Chekuri, Rajeev Motwani: Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine. Discrete Applied Mathematics 98(1-2): 29-38 (1999)

Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. J. Algorithms 33(1): 73-91 (1999)

Donald Aingworth, Chandra Chekuri, Piotr Indyk, Rajeev Motwani: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). SIAM J. Comput. 28(4): 1167-1181 (1999)

Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko: Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS 1999: 32-44

Chandra Chekuri, Sanjeev Khanna: On Multi-Dimensional Packing Problems. SODA 1999: 185-194

Chandra Chekuri, Rajeev Motwani: Minimizing Weighted Completion Time on a Single Machine. SODA 1999: 873-874

Michael A. Bender, Chandra Chekuri: Performance Guarantees for the TSP with a Parameterized Triangle Inequality. WADS 1999: 80-85

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin: Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS 1998: 379-388

Chandra Chekuri, Michael A. Bender: An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines. IPCO 1998: 383-393

Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. SODA 1998: 192-200

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha: Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median. STOC 1998: 114-123

Narayanan Shivakumar, Hector Garcia-Molina, Chandra Chekuri: Filtering with Approximate Predicates. VLDB 1998: 263-274

Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70

Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Clifford Stein: Experimental Study of Minimum Cut Algorithms. SODA 1997: 324-333

Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein: Approximation Techniques for Average Completion Time Scheduling. SODA 1997: 609-618

Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani: Incremental Clustering and Dynamic Information Retrieval. STOC 1997: 626-635

Chandra Chekuri, Richard Johnson, Rajeev Motwani, B. Natarajan, B. Ramakrishna Rau, Michael S. Schlansker: Profile-driven Instruction Level Parallel Scheduling with Application to Super Blocks. MICRO 1996: 58-67

Donald Aingworth, Chandra Chekuri, Rajeev Motwani: Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication). SODA 1996: 547-553

Chandra Chekuri, Waqar Hasan, Rajeev Motwani: Scheduling Problems in Parallel Query Optimization. PODS 1995: 255-265