Publications

  • Reducing the rank of a matroid
    Submitted.
    (with Gwenael Joret)

  • Non-redistributive second welfare theorems.
    Proceedings of 8th Workshop on Internet & Network Economics (WINE), pp247-243, 2012.
    (with Bundit Laekhanukit and Guyslain Naves)

  • A Theoretical Examination of Practical Game Playing: Lookahead Search.
    Proceedings of 5th International Symposium on Algorithmic Game Theory (SAGT), 251-262, 2012.
    (with Vahab Mirrokni and Nithum Thain)

  • Routing regardless of network stability
    Proceedings of the 20th European Symposia on Algorithms (ESA), 719-730, 2012.
    (with Bundit Laekhanukit and Gordon Wilfong)

  • Simultaneous clustering.
    Submitted.
    (with Zhentao Li and Manikandan Narayanan)

  • Approximating rooted steiner networks.
    Proceedings of the 23rd Symposium on Discrete Algorithms (SODA), pp1499-1511, 2012.
    (with Joseph Cheriyan, Bundit Laekhanukit and Guyslain Naves)

  • Computation in causal graphs.
    Submitted.
    (with Juli Atherton and Derek Ruths)

  • Clique cover on sparse networks.
    Proceedings of 14th Workshop on Algorithm Engineering and Experiments (ALENEX), pp93-102, 2012.
    (with Mathieu Blanchette and Ethan Kim)

  • A minmax theorem for non-interfering flows and galaxy cutsets in planar graphs.
    Submitted.
    (with Nicolas Sonnerat)

  • Predicting direct protein interactions from affinity purification mass spectrometry data.
    Algorithms for Molecular Biology, 5(34), 2010.
    (with Mathieu Blanchette, Ethan Kim and Ashish Sabharwal)

  • On the efficiency of markets with two-sided proportional allocation mechanisms.
    Proceedings of 3rd International Symposium on Algorithmic Game Theory (SAGT), pp246-261, 2010.
    (with Volodymyr Kuleshov)

  • Maximum flows on disjoint paths.
    Proceedings of 13th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp326-337, 2010.
    (with Guyslain Naves and Nicolas Sonnerat)

  • Bounds on the cleaning times of robot vacuums.
    Operations Research Letters, 38(1), pp69-71, 2010.
    (with Zhentao Li)

  • Galaxy cutsets in graphs.
    Journal of Combinatorial Optimization, 19(3), pp415-427, 2010.
    (with Nicolas Sonnerat)
    [A preliminary version appeared in Proceedings of International Symposium on Combinatorial Optimization (CO), 2008.]

  • Simultaneous clustering of multiple gene expression and physical interaction datasets.
    PLoS Computational Biology, 6(4), 2010.
    [A preliminary version appeared in Research in Computational Molecular Biology - Regulatory Genomics (RECOMB-RG), 2009.]
    Supplementary Text and JointCluster Software.
    (with Manikandan Narayanan, Eric Schadt and Jun Zhu)

  • An approximation algorithm for the maximum leaf spanning arborescence problem.
    ACM Transactions on Algorithms, 6(3), 2010.
    (with Matthew Drescher)

  • Computational aspects of multimarket price wars.
    Proceedings of 5th Workshop on Internet & Network Economics (WINE), pp304-315, 2009.
    (with Nithum Thain)

  • Defending planar graphs against star-cutsets.
    European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), 2009.
    (with Nicolas Sonnerat)

  • On the odd-minor variant of Hadwiger's conjecture.
    Journal of Combinatorial Theory Series B, 99, pp20-29, 2009.
    (with Jim Geelan, Bert Gerards, Bruce Reed and Paul Seymour)

  • A priority-based model of routing.
    Chicago Journal of Theoretical Computer Science, Article #1, 29 pages, 2008.
    (with Babak Farzad and Neil Olver)

  • Planar graph bipartization in linear time.
    Discrete Applied Mathematics, 156(7), pp1175-1180, 2008.
    (with Samuel Fiorini, Nadia Hardy and Bruce Reed)
    [A preliminary version appeared in Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO), pp226-232, 2005.]

  • Network connectivity and malicious attacks.
    Submitted.
    (with Nicolas Sonnerat)

  • Degree-constrained network flows.
    Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), pp681-688, 2007.
    (with Patrick Donovan, Bruce Shepherd and Gordon Wilfong)

  • A polynomial-time algorithm for finding Nash equilibria in planar win-lose games.
    Journal of Graph Algorithms and Applications, 11(1), pp309-319, 2007.
    (with Louigi Addario-Berry and Neil Olver)

  • An upper bound for the chromatic number of line graphs.
    European Journal of Combinatorics, 28(8), pp2182-2187, 2007.
    (with Andrew King and Bruce Reed)
    [A preliminary version appeared in Proceedings of European Conference of Combinatorics, Graph Theory and Applications (EuroComb), 2005.]

  • Approximate min-max relations for odd cycles in planar graphs.
    Mathematical Programming B, 110(1), pp71-91, 2007.
    (with Samuel Fiorini, Nadia Hardy and Bruce Reed)
    [A preliminary version appeared in Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp35-50, 2005.]

  • Nash equilibria in random games.
    Random Structures and Algorithms, 31(4), pp391-405, 2007.
    (with Imre Barany and Santosh Vempala)
    [A preliminary version appeared in Proceedings of the 46th Symposium on the Foundations of Computer Science (FOCS), pp123-131, 2005.]

  • (Almost) tight bounds and existence theorems for single-commodity confluent flows.
    Journal of the ACM, 54(4), Article 16, 32 pages, 2007.
    (with Jiangzhou Chen, Robert Kleinberg, Laszlo Lovasz, Rajmohan Rajaraman and Ravi Sundaram)
    [A preliminary version appeared in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp529-538, 2004.]

  • The demand matching problem.
    Mathematics of Operations Research, 32, pp563-578, 2007.
    (with Bruce Shepherd)
    [A preliminary version appeared in Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp457-476, 2002.]

  • Network design via iterative rounding of setpair relaxations.
    Combinatorica, 26(3), pp255-275, 2006.
    (with Joseph Cheriyan and Santosh Vempala)

  • Sink equilibria and convergence.
    Proceedings of the 46th Symposium on the Foundations of Computer Science (FOCS), pp142-154, 2005.
    (with Michel Goemans and Vahab Mirrokni)

  • Approximation algorithms for network design with metric costs.
    SIAM Journal on Discrete Mathematics, 21(3), pp612-636, 2007.
    (with Joseph Cheriyan)
    [A preliminary version appeared in Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), pp167-175, 2005.]

  • Visualizing, finding and packing dijoins.
    In D. Avis, A. Hertz and O. Marcotte (Eds.), Graph Theory and Combinatorial Optimization, Kluwer, pp219-254, 2005.
    (with Bruce Shepherd)

  • Convergence issues in competitive games.
    Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp183-194, 2004.
    (with Vahab Mirrokni)

  • Lighting fibers in a dark network.
    Journal on Selected Areas in Communications, 22(9), pp1583-1588, 2004.
    (with Bruce Shepherd)

  • Finding odd cycle transversals.
    Operations Research Letters, 32, pp299-301, 2004.
    (with Bruce Reed and Kaleigh Smith)

  • On clusterings: good, bad and spectral.
    Journal of the ACM, 51(3), pp497-515, 2004.
    (with Ravi Kannan and Santosh Vempala)
    [A preliminary version appeared in Proceedings of the 41st Symposium on the Foundations of Computer Science (FOCS), pp367-377, 2000.]

  • Approximation algorithms for minimum-cost k-vertex connected subgraphs.
    SIAM Journal on Computing, 32(4), pp1050-1055, 2003.
    (with Joseph Cheriyan and Santosh Vempala)
    [A preliminary version appeared in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), pp306-312, 2002.]

  • Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions.
    Proceedings of the 43rd Symposium on the Foundations of Computer Science (FOCS), pp416-425, 2002.

  • Approximating the minimum strongly connected subgraph via a matching lower bound.
    Proceedings of the 12th Symposium on Discrete Algorithms (SODA), pp417-426, 2001.

  • Factor 4/3 approximations for minimum two-connected subgraphs.
    Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp262-73, 2000.
    (with Santosh Vempala)

  • Misconceptions of biometrical IQists.
    Cahiers de Psychologie Cognitive, 18(2), pp115-60, 1999.
    (with Christiane Capron, Michel Duyme and Atam Vetta)

  • Graph connectivity: relaxations and algorithms.
    Ph.D. Thesis, Massachusetts Institute of Technology, June 2002.