Publications

  • The finite horizon, undiscounted, durable goods monopoly problem with finitely many consumers.
    Journal of Mathematical Economics}, 82, pp171-183, 2019.
    (with Gerardo Berbeglia and Peter Sloan)
    [A preliminary version appeared in Proceedings of 10th Conference on Web and Internet Economics (WINE), pp292-293, 2014.]

  • Risk-free bidding in complement-free combinatorial auctions.
    To appear in Proceedings of 9th International Symposium on Algorithmic Game Theory (SAGT), 2019.
    (with Vishnu Narayan, and Gautam Rayaprolu)

  • The declining price anomaly is not universal in multi-buyer sequential auctions (but almost is).
    To appear in Proceedings of 9th International Symposium on Algorithmic Game Theory (SAGT), 2019.
    (with Vishnu Narayan and Eungurrand Prebet)

  • Pricing policies for selling indivisible storable goods to strategic consumers.
    Annals of Operations Research, 274(1-2), pp131-154, 2019.
    (with Gerardo Berbeglia and Gautam Rayaprolu)
    [A preliminary version appeared in Proceedings of 11th Conference on Web and Internet Economics (WINE), 2015.]

  • Computation in causal graphs.
    Journal of Graph Algorithms and Applications, 23(2), pp317-344, 2019.
    (with Juli Atherton and Derek Ruths )

  • A factor 4/3 approximation algorithm for the minimum 2-edge connected subgraph problem.
    To appear in ACM Transactions on Algorithms, 2019.
    (with Christoph Hunkenschröder and Santosh Vempala)
    [A preliminary version appeared in Proceedings of 3rd Conference Approximation Algorithms for Combinatorial Optimization (APPROX), pp262-273, 2000.]

  • Fair division in hereditary systems.
    Proceedings of 14th Conference on Web and Internet Economics (WINE)}, pp297-311, 2018.
    (with Zhentao Li)

  • Tight bounds on the relative performances of pricing mechanisms in storable good markets.
    Proceedings of 8th International Symposium on Algorithmic Game Theory (SAGT), pp267-271, 2018. (with Gerardo Berbeglia and Shant Boodaghians)

  • The combinatorial clock auction: the effects of strategic behaviour and the price increment rule on social welfare.
    Proceedings of 19th ACM Conference on Economics and Computation (EC), pp91-108, 2018.
    (with Max Dupré la Tour)

  • The inapproximability of maximum single-sink unsplittable, priority and confluent flows.
    Theory of Computing, 13(20), pp1-25, 2017.
    (with Bruce Shepherd)

  • The economic efficiency of the combinatorial clock auction.
    Proceedings of 27th Symposium on Discrete Algorithms (SODA), pp1407-1423, 2016.
    (with Nicolas Bousquet, Yang Cai and Christoph Hunkenschröder)

  • Welfare and rationality guarantees for the simultaneous multiple-round ascending auction.
    Proceedings of 11th Conference on Web and Internet Economics (WINE), pp216-229, 2015.
    (with Nicolas Bousquet and Yang Cai)

  • Testing consumer rationality using perfect graphs and oriented discs.
    Proceedings of 11th Conference on Web and Internet Economics (WINE), pp187-200, 2015.
    (with Shant Boodaghians)

  • Polylogarithmic approximations for the capacitated single-sink confluent flow problem.
    Proceedings of the 56th Symposium on the Foundations of Computer Science (FOCS), pp748-758, 2015.
    (with Bruce Shepherd and Gordon Wilfong)

  • The combinatorial world (of auctions) according to GARP.
    Proceedings of 8th International Symposium on Algorithmic Game Theory (SAGT), pp125-136, 2015.
    (with Shant Boodaghians)

  • Reducing the rank of a matroid.
    Discrete Mathematics & Theoretical Computer Science, 17(2), pp143-156, 2015.
    (with Gwenaël Joret)

  • Large supports are required for well-supported Nash equilibria.
    Proceedings of 18th on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp78-84, 2015.
    (with Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin and Hehui Wu)

  • Coalition games on interaction graphs: a horticultural perspective.
    Proceedings of 16th ACM Conference on Economics and Computation (EC), pp95-112, 2015.
    (with Nicolas Bousquet and Zhentao Li)

  • A near-optimal mechanism for impartial selection.
    Proceedings of 10th Conference on Web and Internet Economics (WINE), pp133-146, 2014.
    (with Nicolas Bousquet and Sergey Norin)

  • Bounds on the profitability of a durable good monopolist.
    Proceedings of 10th Conference on Web and Internet Economics (WINE), pp292-293, 2014.
    (with Gerardo Berbeglia and Peter Sloan)

  • To save or not to save: the Fisher game.
    Proceedings of 10th Conference on Web and Internet Economics (WINE), pp294-307, 2014.
    (with Ruta Mehta, Nithum Thain and Laszlo Vegh)

  • Randomized experimental design for causal graph discovery.
    Proceedings of the Neural Information Processing Systems Conference (NIPS), pp2339-2347, 2014.
    (with Huining Hu and Zhentao Li)

  • Routing regardless of network stability.
    Algorithmica, 70(3), pp561-593, 2014.
    (with Bundit Laekhanukit and Gordon Wilfong)
    [A preliminary version appeared in Proceedings of the 20th European Symposia on Algorithms (ESA), pp719-730, 2012.]

  • Approximating rooted steiner networks.
    ACM Transactions on Algorithms, 11(2), #8, 2014.
    (with Joseph Cheriyan, Bundit Laekhanukit and Guyslain Naves)
    [A preliminary version appeared in Proceedings of the 23rd Symposium on Discrete Algorithms (SODA), pp1499-1511, 2012.]

  • False-name bidding and economic efficiency in combinatorial auctions.
    Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI), pp2339-2347, 2014.
    (with Colleen Alkalay-Houlihan)

  • The complexity of the simultaneous cluster problem.
    Journal of Graph Algorithms and Applications, 18(1), pp1-34, 2014.
    (with Zhentao Li and Manikandan Narayanan)

  • Polylogarithmic supports are required for approximate well-supported Nash equilibria below 2/3.
    Proceedings of 9th Conference on Web and Internet Economics (WINE), pp15-23, 2013.
    (with Yogesh Anbalagan, Sergey Norin and Rahul Savani)

  • 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), pp251-262, 2012.
    (with Vahab Mirrokni and Nithum Thain)

  • 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.
    (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 Problems (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.
    (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 Problems (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.

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