-
Chapter and Conference Paper
A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP
We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic \(3/2-\epsilon \)
-
Chapter and Conference Paper
Competition Alleviates Present Bias in Task Completion
We build upon recent work by Kleinberg, Oren, and Raghavan [10–12] that considers present biased agents, who place more weight on costs they must incur now than costs they will incur in the future. They consider ...
-
Chapter and Conference Paper
Carpooling in Social Networks
We consider the online carpool fairness problem of Fagin–Williams (IBM J Res Dev 27(2):133–139, 1983), where an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. Th...
-
Chapter and Conference Paper
A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
Recent work by Babaioff et al. [1], Yao [30], and Cai et al. [7] shows how to construct an approximately optimal auction for additive bidders, given access to the priors from which the bidders’ values are drawn. ...
-
Chapter and Conference Paper
On Revenue Maximization for Agents with Costly Information Acquisition
A prevalent assumption in traditional mechanism design is that buyers know their precise value for an item; however, this assumption is rarely true in practice. In most settings, buyers can “deliberate”, i.e.,...
-
Chapter and Conference Paper
Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
In this paper, we study the integrality gap of the Knapsack linear program in the Sherali-Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 – ε persists up to a linear number of rounds o...
-
Chapter and Conference Paper
On Revenue Maximization in Second-Price Ad Auctions
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auction, which does not realistic...
-
Chapter and Conference Paper
Approximating Matches Made in Heaven
Motivated by applications in online dating and kidney exchange, we study a stochastic matching problem in which we have a random graph G given by a node set V and probabilities p(i,j) on all pairs i,j ∈ V represe...
-
Chapter and Conference Paper
Improved Approximation Algorithms for Budgeted Allocations
We provide a 3/2-approximation algorithm for an offline budgeted allocations problem with applications to sponsored search auctions. This an improvement over the e/(e − 1) approximation of Andelman and Mansour [1...
-
Chapter and Conference Paper
On the Equilibria and Efficiency of the GSP Mechanism in Keyword Auctions with Externalities
In the increasingly important market of online search advertising, a multitude of parameters affect the performance of advertising campaigns and their ability to attract users’ attention enough to produce clic...
-
Chapter and Conference Paper
Ad Auctions – Current and Future Research
An exploding market has emerged during the last few years on the internet, the market of sponsored search slots. Advertisers are able to buy space on the webpages produced by popular search engines and place a...
-
Chapter and Conference Paper
A Lower Bound on the Competitive Ratio of Truthful Auctions
We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal s...
-
Chapter and Conference Paper
Mechanism Design for Fun and Profit
The emergence of the Internet as one of the most important arenas for resource sharing between parties with diverse and selfish interests has led to a number of fascinating and new algorithmic problems. In the...
-
Chapter and Conference Paper
Truthful and Competitive Double Auctions
In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder’s utility value for the item ...
-
Chapter and Conference Paper
Dynamically Fault-Tolerant Content Addressable Networks
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an arbitrarily lar...
-
Chapter and Conference Paper
Web Search via Hub Synthesis
We present a probabilistic generative model for web search which captures in a unified manner three critical components of web search: how the link structure of the web is generated, how the content of a web d...
-
Chapter and Conference Paper
Spectral Analysis for Data Mining
Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents i...
-
Chapter and Conference Paper
An Experimental Study of Data Migration Algorithms
The data migration problem is the problem of computing a plan for moving data objects stored on devices in a network from one configuration to another. Load balancing or changing usage patterns might necessitate ...
-
Chapter and Conference Paper
On List Update and Work Function Algorithms
The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the...
-
Chapter
On the performance of competitive algorithms in practice
