Sponsored Search Auctions with Markovian Users (2009)
Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Martin Pál
Abstract. Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. The most popular auction for sponsored...
Stochastic Steiner trees without a root (2009)
Abstract. This paper considers the Steiner tree problem in the model of twostage stochastic optimization with recourse. This model, the focus of much recent research [1–4], tries to capture the...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál
Abstract. We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as...
Education and Employment (2008)
Martin Pál, Google Inc, Éva Tardos
Search advertising auction dynamics, auction design and bidding strategies, game theory, approximation
ABSTRACT Boosted Sampling: Approximation Algorithms for Stochastic Optimization (2008)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for...
An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem ∗ (2007)
Chandra Chekuri, Martin Pál, C. Chekuri, M. Pál
Abstract: We consider a variant of the traveling salesman problem (TSP): Given a directed graph G = (V,A) with non-negative arc lengths ℓ: A → R + and a pair of vertices s,t, find an s-t walk of...
Maximizing a Submodular Set Function subject to a Matroid Constraint (2007)
Gruia Calinescu, Ra Chekuri, Martin Pál, Jan Vondrák
Abstract. Let f: 2 N → R + be a non-decreasing submodular set function, and let (N, I) be a matroid. We consider the problem maxS∈I f(S). It is known that the greedy algorithm yields a...
Stochastic models for budget optimization in search-based. manuscript (2007)
S. Muthukrishnan, Martin Pál, Zoya Svitkina
Internet search companies sell advertisement slots based on users ’ search queries via an auction. Advertisers have to determine how to place bids on the keywords of their interest in order to...
Maximizing a Submodular Set Function subject to a Matroid Constraint (2007)
Gruia Calinescu, Ra Chekuri, Martin Pál, Jan Vondrák
Abstract. Let f: 2 N → R + be a non-decreasing submodular set function, and let (N, I) be a matroid. We consider the problem maxS∈I f(S). It is known that the greedy algorithm yields a...
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina
Abstract. We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the...
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina
Abstract. We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the...
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina
Abstract. We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the...
Sampling bounds for stochastic optimization (2005)
Moses Charikar, Ra Chekuri, Martin Pál
Abstract. A large class of stochastic optimization problems can be modeled as minimizing an objective function f that depends on a choice of a vector x ∈ X, as well as on a random external...
Approximation algorithms for stochastic inventory control models (2005)
Retsef Levi, Martin Pál, Robin O. Roundy, David B. Shmoys
In this paper we address the long-standing problem of finding computationally efficient and provably good inventory control policies in supply chains with correlated and nonstationary...
What about Wednesday? approximation algorithms for multistage stochastic optimization (2005)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Abstract. The field of stochastic optimization studies decision making under uncertainty, when only probabilistic information about the future is available. Finding approximate solutions to...
Boosted sampling: Approximation algorithms for stochastic optimization (2004)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the STEINER TREE...
A.: Boosted sampling: Approximation algorithms for stochastic optimization problems (2004)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for...
Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of...
Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of...