Route Planning under Uncertainty: The Canadian Traveller Problem (2009)
Evdokia Nikolova, David R. Karger
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an optimal policy that...
VCG overpayment in random graphs (2009)
David R. Karger, Evdokia Nikolova
Motivated by the increasing need to price networks, we study the prices resulting from of a variant of the VCG mechanism, specifically defined for networks [11]. This VCG mechanism is the unique...
Nicole Immorlica, Evdokia Nikolova
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the...
On the Hardness and Smoothed Complexity of Quasi-Concave Minimization (2008)
Jonathan A. Kelner, Evdokia Nikolova
In this paper, we resolve the smoothed and approximative complexity of low-rank quasi-concave minimization, providing both upper and lower bounds. As an upper bound, we provide the first smoothed...
General Terms: Economics, Theory. (2008)
David Karger, Evdokia Nikolova
The VCG mechanism for buying a path from s to t in a network with selfish edges, selects the lowest-cost path (LCP) and pays each edge e on the path the edge’s cost plus a bonus equal to the...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova
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...
ABSTRACT A Strategic Model for Information Markets (2008)
Information markets, which are designed specifically to aggregate traders ’ information, are becoming increasingly popular as a means for predicting future events. Recent research in information...
Stochastic Combinatorial Optimization with Risk (2008)
We consider general combinatorial optimization problems that can be formulated as minimizing the weight of a feasible solution wT x over an arbitrary feasible set. For these problems we describe a...
Stochastic Combinatorial Optimization with Risk (2008)
We consider general combinatorial optimization problems that can be formulated as minimizing the weight of a feasible solution wT x over an arbitrary feasible set. For these problems we describe a...
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...
Incentive-Compatible Interdomain Routing with Linear Utilities ⋆ (2008)
Er Hall, Evdokia Nikolova, Christos Papadimitriou
Abstract. We revisit the problem of incentive-compatible interdomain routing, examining the, quite realistic, special case in which the autonomous systems ’ (ASes’) utilities are linear functions...
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2008)
Karger, David, Nikolova, Evdokia
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy...
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2008)
Karger, David, Nikolova, Evdokia
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Feldman, Jon, Muthukrishnan, S., Nikolova, Evdokia, Pal, Martin
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 well...
Betting on permutations (2007)
Yiling Chen, Evdokia Nikolova, Lance Fortnow
We consider a permutation betting scenario, where people wager on the final ordering of n candidates: for example, the outcome of a horse race. We examine the auctioneer problem of risklessly...
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (2007)
David Karger, Evdokia Nikolova, David Karger, Evdokia Nikolova
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy...
Stochastic shortest paths via quasi-convex maximization (2006)
Evdokia Nikolova, Jonathan A. Kelner, Matthew Br, Michael Mitzenmacher
Abstract. We consider the problem of finding shortest paths in a graph with independent randomly distributed edge lengths. Our goal is to maximize the probability that the path length does not exceed...
Stochastic shortest paths via quasi-convex maximization (2006)
Evdokia Nikolova, Jonathan A. Kelner, Matthew Br, Michael Mitzenmacher
Abstract. We consider the problem of finding shortest paths in a graph with independent randomly distributed edge lengths. Our goal is to maximize the probability that the path length does not exceed...
Optimal route planning under uncertainty (2006)
We present new complexity results and efficient algorithms for optimal route planning in the presence of uncertainty. We employ a decision theoretic framework for defining the optimal route: for a...
First-price path auctions (2005)
Nicole Immorlica, Evdokia Nikolova, David Karger, Rahul Sami
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the...