6 papers
Asymmetric Trading Prophets
Gagan Aggarwal, Anupam Gupta, Yifan Wang +1
The "Trading Prophet" problem challenges an online trader to maximize its profit by buying and selling assets under stochastic prices and capacity constraints, competing against an…
Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta, Vera Traub
In the Steiner Forest problem, we are given a graph with edge lengths, and a collection of demand pairs; the goal is to find a subgraph of least total length such that each demand…
A Learning Perspective on Random-Order Covering Problems
Anupam Gupta, Marco Molinaro, Matteo Russo
In the random-order online set cover problem, the instance with sets and elements is chosen in a worst-case fashion, but then the elements arrive in a uniformly random orde…
Why is My Route Different Today? An Algorithm for Explaining Route Selection
Aaron Schild, Sreenivas Gollapudi, Anupam Gupta +2
Users of routing services like Apple Maps, Google Maps, and Waze frequently wonder why a given route is proposed. This question particularly arises when dynamic conditions like tra…
Multi-Platform Autobidding with and without Predictions
Gagan Aggarwal, Anupam Gupta, Xizhi Tan +1
We study the problem of finding the optimal bidding strategy for an advertiser in a multi-platform auction setting. The competition on a platform is captured by a value and a cost…
Randomized Truthful Auctions with Learning Agents
Gagan Aggarwal, Anupam Gupta, Andres Perlroth +1
We study a setting where agents use no-regret learning algorithms to participate in repeated auctions. \citet{kolumbus2022auctions} showed, rather surprisingly, that when bidders p…