We present a truthful auction for pricing advertising slots on web-page assuming that advertisements different merchants must be ranked in decreasing order of their (weighted) bids. This captures both the Overture model where bidders are submitted bids, and Google expected revenue (or utility) advertisement generates. Assuming separable click-through rates, we prove revenue-equivalence between our non-truthful next-price auctions currently use.

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is problem of increasing importance today. The traditional approach de-identifying records to remove identifying fields such as social security number, name etc. However, recent research has shown that large fraction the US population can be identified using non-key attributes (called quasi-identifiers) date birth, gender, and zip code [15]. Sweeney [16] proposed k-anonymity model...

In this paper, we study the complexity of self-assembly under models that are natural generalizations tile model. particular, extend Rothemund and Winfree's [Proceedings 32nd Annual ACM Symposium on Theory Computing, Portland, OR, 2000, pp. 459--468]. They provided a lower bound $\Omega(\frac{\log N}{\log\log N})$ assembling an $N\times N$ square for almost all N. Adleman et al. 33rd Heraklion, Greece, 2001, 740--748] gave construction which achieves bound. We consider whether can be reduced...

We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a graph. The vertices in U have weights and are known ahead of time, while V arrive an arbitrary order to be matched upon arrival. goal maximize sum U. When all equal, this reduces classic problem for which Karp, Vazirani gave optimal (1−1/e)-competitive algorithm their seminal work [10].Our main result randomized general vertex weights. use random perturbations by appropriately chosen multiplicative...

Previous chapter Next Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted AllocationsGagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak MehtaGagan Mehtapp.1253 - 1264Chapter DOI:https://doi.org/10.1137/1.9781611973082.95PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study following vertex-weighted online bipartite matching...

In sponsored search, a number of advertising slots is available on search results page, and have to be allocated among set advertisers competing display an ad the page. This gives rise bipartite matching market that typically cleared by way automated auction. Several auction mechanisms been proposed, with variants Generalized Second Price (GSP) being widely used in practice. There rich body work markets builds upon stable marriage model Gale Shapley assignment Shubik. line research offers...

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is problem of increasing importance today. The traditional approach deidentifying records to remove identifying fields such as social security number, name, etc. However, recent research has shown that large fraction the U.S. population can be identified using nonkey attributes (called quasi-identifiers) date birth, gender, and zip code. k -anonymity model protects privacy via...

We consider a game theoretic knapsack problem that has application to auctions for selling advertisements on Internet search engines. Consider n agents each wishing place an object in the knapsack. Each agent private valuation having their and publicly known size. For this setting, we design of which have incentive truthfully reveal valuations. Following framework Goldberg et al. [10], look auction obtains constant fraction profit obtainable by natural optimal pricing algorithm knows agents'...

The need to deal with massive data sets in many practical applications has led a growing interest computational models appropriate for large inputs. most important quality of realistic model is that it can be efficiently implemented across wide range platforms and operating systems. In this paper, we study the results if streaming augmented sorting primitive. We argue highly practical, problems solved (relatively weak) model. Examples are undirected connectivity, minimum spanning trees,...

We study the problem of designing seller-optimal auctions, i.e. auctions where objective is to maximize revenue. Prior this work, only known be approximately optimal in worst case employed randomization. Our main result existence deterministic that match performance guarantees these randomized auctions. give a fairly general derandomization technique for turning any mechanism into an asymmetric one with same In doing so, we bypass impossibility symmetric and show asymmetry nearly as powerful...

In this paper, we extend Rothemund and Winfree's examination of the tile complexity self-assembly [6]. They provided a lower bound Ω(log N/log log N) on assembling an N × square for almost all N. Adleman et al. [1] gave construction which achieves bound. We consider whether can be reduced through several natural generalizations model. One our results is set size O(√log assembles in model allows flexible glue strength between non-equal glues (This was independently discovered [3]). This...

In the classical load balancing or multiprocessor scheduling problem, we are given a sequence of jobs varying sizes and asked to assign each job one m empty processors. A typical objective is minimize makespan, on heaviest loaded processor. Since in most real world scenarios dynamic measure, initial assignment may be not remain optimal with time. Motivated by such considerations variety systems, formulate problem rebalancing --- possibly suboptimal processors, relocate set so as decrease...

The essence of an Internet router is n /spl times/ switch which routes packets from input to output ports. Such a can be viewed as bipartite graph with the and ports two vertex sets. Packets arriving at port i destined for j modeled edge j. Current scheduling algorithms view routing each time step selection matching. We take that problem across sequence time-steps instance coloring multigraph. Implementation considerations lead us seek multigraphs are fast, decentralized, online. present...

We consider a game theoretic knapsack problem that has application to auctions for selling advertisements on Internet search engines. Consider n agents each wishing place an object in the knapsack. Each agent private valuation having their and publicly known size. For this setting, we design of which have incentive truthfully reveal valuations. Following framework Goldberg et al. [10], look auction obtains constant fraction profit obtainable by natural optimal pricing algorithm knows agents'...