Search results

  • 2015

    Centrality of trees for capacitated k-center

    An, H. C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V. & Svensson, O., Dec 1 2015, In: Mathematical Programming. 154, 1-2, p. 29-53 25 p.

    Research output: Contribution to journalArticlepeer-review

    Open Access
  • Degree-3 treewidth sparsifiers

    Chekuri, C. & Chuzhoy, J., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 242-255 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Delay-constrained unicast and the triangle-cast problem

    Chekuri, C., Kamath, S., Kannan, S. & Viswanath, P., Sep 28 2015, Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., p. 804-808 5 p. 7282566. (IEEE International Symposium on Information Theory - Proceedings; vol. 2015-June).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Multicommodity flows and cuts in polymatroidal networks

    Chekuri, C., Kannan, S., Raja, A. & Viswanath, P., 2015, In: SIAM Journal on Computing. 44, 4, p. 912-943 32 p.

    Research output: Contribution to journalArticlepeer-review

    Open Access
  • On element-connectivity preserving graph simplification

    Chekuri, C., Rukkanchanunt, T. & Xu, C., 2015, Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Bansal, N. & Finocchi, I. (eds.). Springer, p. 313-324 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9294).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • On multiplicative weight updates for concave and submodular function maximization [extended abstract]

    Chekuri, C., Jayram, T. S. & Vondrák, J., Jan 11 2015, ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science. Association for Computing Machinery, p. 201-210 10 p. (ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Streaming algorithms for submodular function maximization

    Chekuri, C., Gupta, S. & Quanrud, K., 2015, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Halldorsson, M. M., Kobayashi, N., Speckmann, B. & Iwama, K. (eds.). Springer, p. 318-330 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9134).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • The all-or-nothing flow problem in directed graphs with symmetric demand pairs

    Chekuri, C. & Ene, A., Dec 1 2015, In: Mathematical Programming. 154, 1-2, p. 249-272 24 p.

    Research output: Contribution to journalArticlepeer-review

    Open Access
  • 2014

    A graph reduction step preserving element-connectivity and packing steiner trees and forests

    Chekuri, C. & Korula, N., 2014, In: SIAM Journal on Discrete Mathematics. 28, 2, p. 577-597 21 p.

    Research output: Contribution to journalArticlepeer-review

  • Centrality of trees for capacitated k-center

    An, H. C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V. & Svensson, O., 2014, Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings. Springer, p. 52-63 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8494 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Polynomial bounds for the Grid-Minor Theorem

    Chekuri, C. & Chuzhoy, J., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 60-69 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Chekuri, C., Vondrák, J. & Zenklusen, R., 2014, In: SIAM Journal on Computing. 43, 6, p. 1831-1879 49 p.

    Research output: Contribution to journalArticlepeer-review

    Open Access
  • The all-or-nothing flow problem in directed graphs with symmetric demand pairs

    Chekuri, C. & Ene, A., 2014, Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings. Springer, p. 222-233 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8494 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • 2013

    Approximation algorithms for Euler genus and related problems

    Chekuri, C. & Sidiropoulos, A., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 167-176 10 p. 6686152. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Flow-cut gaps for integer and fractional multiflows

    Chekuri, C., Shepherd, F. B. & Weibel, C., Mar 2013, In: Journal of Combinatorial Theory. Series B. 103, 2, p. 248-273 26 p.

    Research output: Contribution to journalArticlepeer-review

  • Large-treewidth graph decompositions and applications

    Chekuri, C. & Chuzhoy, J., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 291-300 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Maximum edge-disjoint paths in k-sums of graphs

    Chekuri, C., Naves, G. & Shepherd, F. B., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 328-339 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

    Chekuri, C. & Ene, A., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, p. 326-341 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2012

    Improved algorithms for orienteering and related problems

    Chekuri, C., Korula, N. & Pal, M., Jul 2012, In: ACM Transactions on Algorithms. 8, 3, 23.

    Research output: Contribution to journalArticlepeer-review

  • Multicommodity flows and cuts in polymatroidal networks

    Chekuri, C., Kannan, S., Raja, A. & Viswanath, P., 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 399-408 10 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Node-weighted network design in planar and minor-closed families of graphs

    Chekuri, C., Ene, A. & Vakilian, A., 2012, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 ed. p. 206-217 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7391 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • On the set multicover problem in geometric settings

    Chekuri, C., Clarkson, K. L. & Har-Peled, S., Dec 2012, In: ACM Transactions on Algorithms. 9, 1, 9.

    Research output: Contribution to journalArticlepeer-review

  • Prize-collecting survivable network design in node-weighted graphs

    Chekuri, C., Ene, A. & Vakilian, A., 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. p. 98-109 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Pruning 2-connected graphs

    Chekuri, C. & Korula, N., Feb 2012, In: Algorithmica (New York). 62, 1-2, p. 436-463 28 p.

    Research output: Contribution to journalArticlepeer-review

  • 2011

    Approximability of capacitated network design

    Chakrabarty, D., Chekuri, C., Khanna, S. & Korula, N., 2011, Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings. p. 78-91 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6655 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Approximation algorithms for submodular multiway partition

    Chekuri, C. & Ene, A., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 807-816 10 p. 6108251. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Buy-at-bulk network design with protection

    Antonakopoulos, S., Chekuri, C., Shepherd, B. & Zhang, L., Feb 2011, In: Mathematics of Operations Research. 36, 1, p. 71-87 17 p.

    Research output: Contribution to journalArticlepeer-review

  • Maximizing a monotone submodular function subject to a matroid constraint

    Calinescu, G., Chekuri, C., Pál, M. & Vondrák, J., 2011, In: SIAM Journal on Computing. 40, 6, p. 1740-1766 27 p.

    Research output: Contribution to journalArticlepeer-review

  • Multi-budgeted matchings and matroid intersection via dependent rounding

    Chekuri, C., Vondrák, J. & Zenklusen, R., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 1080-1097 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • New models and algorithms for throughput maximization in broadcast scheduling (extended abstract)

    Chekuri, C., Gal, A., Im, S., Khuller, S., Li, J., McCutchen, R., Moseley, B. & Raschid, L., 2011, Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers. p. 71-82 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6534 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Prize-collecting Steiner problems on planar graphs

    Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M. T., Korula, N. & Marx, D., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 1028-1049 22 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

    Chekuri, C., Even, G., Gupta, A. & Segev, D., Mar 2011, In: ACM Transactions on Algorithms. 7, 2, 18.

    Research output: Contribution to journalArticlepeer-review

  • Submodular cost allocation problem and applications

    Chekuri, C. & Ene, A., 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 ed. p. 354-366 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6755 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Submodular function maximization via the multilinear relaxation and contention resolution schemes

    Chekuri, C., Vondrák, J. & Zenklusen, R., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 783-792 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • 2010

    Approximation algorithms for nonuniform buy-at-bulk network design

    Chekuri, C., Hajiaghayi, M. T., Kortsarz, G. & Salavatipour, M. R., 2010, In: SIAM Journal on Computing. 39, 5, p. 1772-1798 27 p.

    Research output: Contribution to journalArticlepeer-review

  • Dependent randomized rounding via exchange properties of combinatorial structures

    Chekuri, C., Vondrák, J. & Zenklusen, R., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 575-584 10 p. 5671314. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Flow-cut gaps for integer and fractional multiflows

    Chekuri, C., Shepherd, F. B. & Weibel, C., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 1198-1208 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • 2009

    A graph reduction step preserving element-connectivity and applications

    Chekuri, C. & Korula, N., 2009, Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1 ed. p. 254-265 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5555 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Algorithmica (New York): Foreword

    Chekuri, C. & Trevisan, L., Sep 2009, In: Algorithmica (New York). 55, 1, p. 111-112 2 p.

    Research output: Contribution to journalEditorialpeer-review

  • A Note on Multiflows and Treewidth

    Chekuri, C., Khanna, S. & Shepherd, F. B., Jul 2009, In: Algorithmica (New York). 54, 3, p. 400-412 13 p.

    Research output: Contribution to journalArticlepeer-review

  • Disjoint bases in a polymatroid

    Cǎlinescu, G., Chekuri, C. & Vondrák, J., Dec 2009, In: Random Structures and Algorithms. 35, 4, p. 418-430 13 p.

    Research output: Contribution to journalArticlepeer-review

  • Edge-disjoint paths in planar graphs with constant congestion

    Chekuri, C., Khanna, S. & Shepherd, F. B., 2009, In: SIAM Journal on Computing. 39, 1, p. 281-301 21 p.

    Research output: Contribution to journalArticlepeer-review

    Open Access
  • Longest wait first for broadcast scheduling

    Chekuri, C., Im, S. & Moseley, B., 2009, Approximation and Online Algorithms - 7th International Workshop, WAOA 2009, Revised Papers. p. 62-74 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5893 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Minimizing maximum response time and delay factor in broadcast scheduling

    Chekuri, C., Im, S. & Moseley, B., 2009, Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings. p. 444-455 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5757 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Online scheduling to minimize the maximum delay factor

    Chekuri, C. & Moseley, B., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 1116-1125 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • On the set multi-cover problem in geometric settings

    Chekuri, C., Clarkson, K. L. & Sariel, H. P., 2009, Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09. p. 341-350 10 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Topology formation for wireless mesh network planning

    Chen, C. C., Chekuri, C. & Klabjan, D., 2009, IEEE INFOCOM 2009 - The 28th Conference on Computer Communications. p. 2671-2675 5 p. 5062209. (Proceedings - IEEE INFOCOM).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Truthful mechanisms via greedy iterative packing

    Chekuri, C. & Gamzu, I., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 56-69 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Unsplittable flow in paths and trees and column-restricted packing integer programs

    Chekuri, C., Ene, A. & Korula, N., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 42-55 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2008

    Algorithms for 2-route cut problems

    Chekuri, C. & Khanna, S., 2008, Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 ed. p. 472-484 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5125 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution