# Nikhil R. Devanur

According to our database

Collaborative distances:

^{1}, Nikhil R. Devanur authored at least 93 papers between 2002 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2020

Optimal multi-unit mechanisms with private demands.

Games Econ. Behav., 2020

Efficient Algorithms for Device Placement of DNN Graph Operators.

CoRR, 2020

Optimal Mechanism Design for Single-Minded Agents.

CoRR, 2020

Algorithmic Price Discrimination.

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Blink: Fast and Generic Collectives for Distributed ML.

Proceedings of Machine Learning and Systems 2020, 2020

2019

Multi-scale Online Learning: Theory and Applications to Online Auctions and Pricing.

J. Mach. Learn. Res., 2019

Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems.

J. ACM, 2019

Bandits with Global Convex Constraints and Objective.

Oper. Res., 2019

Perfect Bayesian Equilibria in repeated sales.

Games Econ. Behav., 2019

Introduction to the Special Issue - Algorithmic Game Theory - STOC/FOCS/SODA 2012.

Games Econ. Behav., 2019

Proportional Dynamics in Exchange Economies.

CoRR, 2019

PipeDream: generalized pipeline parallelism for DNN training.

Proceedings of the 27th ACM Symposium on Operating Systems Principles, 2019

Simple and Approximately Optimal Pricing for Proportional Complementarities.

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018

Revenue Maximization and Ex-Post Budget Constraints.

ACM Trans. Economics and Comput., 2018

Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms.

ACM Trans. Algorithms, 2018

Bubble Execution: Resource-aware Reliable Analytics at Cloud Scale.

Proc. VLDB Endow., 2018

PipeDream: Fast and Efficient Pipeline Parallel DNN Training.

CoRR, 2018

A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems.

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

A report on the workshop on the economics of cloud computing.

SIGecom Exch., 2017

Algorithms and Optimization under Uncertainty (NII Shonan Meeting 2017-5).

NII Shonan Meet. Rep., 2017

Stability of service under time-of-use pricing.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Optimal Mechanism for Selling to a Budget Constrained Buyer: The General Case.

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Truth and Regret in Online Scheduling.

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Online Auctions and Multi-scale Online Learning.

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Convex Program Duality, Fisher Markets, and Nash Social Welfare.

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

2016

Whole-Page Optimization and Submodular Welfare Maximization with Online Bidders.

ACM Trans. Economics and Comput., 2016

A Rational Convex Program for Linear Arrow-Debreu Markets.

ACM Trans. Economics and Comput., 2016

A duality-based unified approach to Bayesian mechanism design.

SIGecom Exch., 2016

New Convex Programs for Fisher's Market Model and its Generalizations.

CoRR, 2016

Multi-Score Position Auctions.

Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, 2016

The sample complexity of auctions with side information.

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Simple Pricing Schemes For Consumers With Evolving Values.

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

ProjecToR: Agile Reconfigurable Data Center Interconnect.

Proceedings of the ACM SIGCOMM 2016 Conference, Florianopolis, Brazil, August 22-26, 2016, 2016

Linear Contextual Bandits with Knapsacks.

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Envy freedom and prior-free mechanism design.

J. Econ. Theory, 2015

Multi-parameter Auctions with Online Supply.

CoRR, 2015

A Market for Scheduling, with Applications to Cloud Computing.

CoRR, 2015

Contextual Bandits with Global Constraints and Objective.

CoRR, 2015

Linear Contextual Bandits with Global Constraints and Objective.

CoRR, 2015

Budget Constraints in Prediction Markets.

Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015

Speed Scaling in the Non-clairvoyant Model.

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Fast Algorithms for Online Stochastic Convex Programming.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Simple Auctions with Simple Strategies.

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014

Online Algorithms for Machine Minimization.

CoRR, 2014

How to sell an app: pay-per-play or buy-it-now?

CoRR, 2014

Removing arbitrage from wagering mechanisms.

Proceedings of the ACM Conference on Economics and Computation, 2014

Bandits with concave rewards and convex knapsacks.

Proceedings of the ACM Conference on Economics and Computation, 2014

2013

On the Approximation of Submodular Functions

CoRR, 2013

Draft Auctions.

CoRR, 2013

Tatonnement beyond gross substitutes?: gradient descent to the rescue.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Cloud scheduling with setup cost.

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Prior-free auctions for budgeted agents.

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Budget smoothing for internet ad auctions: a game theoretic approach.

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2012

Sequential Auctions of Identical Items with Budget-Constrained Bidders

CoRR, 2012

Online matching with concave returns.

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Asymptotically optimal algorithm for stochastic adwords.

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

2011

Online algorithms with stochastic input.

SIGecom Exch., 2011

New geometry-inspired relaxations and algorithms for the metric Steiner tree problem.

Math. Program., 2011

Prior-Independent Multi-parameter Mechanism Design.

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

An O(n log n) Algorithm for a Load Balancing Problem on Paths.

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Distributed algorithms via gradient descent for fisher markets.

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Real-time bidding algorithms for performance-based display ad allocation.

Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011

2010

Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents.

SIAM J. Discret. Math., 2010

Market Equilibrium with Transaction Costs.

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Local Dynamics in Bargaining Networks via Random-Turn Games.

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Monotonicity in Bargaining Networks.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Fast algorithms for finding matchings in lopsided bipartite graphs with applications to display ads.

Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

2009

On competitiveness in uniform utility allocation markets.

Oper. Res. Lett., 2009

An Online Multi-unit Auction with Improved Competitive Ratio.

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

The adwords problem: online keyword matching with budgeted bidders under random permutations.

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

The price of truthfulness for pay-per-click auctions.

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Limited and online supply and the bayesian foundations of prior-free mechanism design.

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach.

SIAM J. Discret. Math., 2008

Market equilibrium via a primal-dual algorithm for a convex program.

J. ACM, 2008

A Computational Theory of Awareness and Decision Making.

Electronic Colloquium on Computational Complexity (ECCC), 2008

Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Computing Market Equilibrium: Beyond Weak Gross Substitutes.

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

2006

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.

Electronic Colloquium on Computational Complexity (ECCC), 2006

New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets.

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Integrality gaps for sparsest cut and minimum linear arrangement problems.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

Strategyproof cost-sharing mechanisms for set cover and facility location games.

Decis. Support Syst., 2005

Price of Anarchy, Locality Gap, and a Network Service Provider Game.

Proceedings of the Internet and Network Economics, First International Workshop, 2005

2004

The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

On the Complexity of Hilbert's 17th Problem.

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003

Extensions of the spending constraint-model: existence and uniqueness of equilibria (extended abstract).

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Who's The Weakest Link?

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2003

An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case.

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

Market Equilibrium via a Primal-Dual-Type Algorithm.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002