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.