We present a novel Locality-Sensitive Hashing scheme for the Approximate Nearest Neighbor Problem under lp norm, based on p-stable distributions.Our improves running time of earlier algorithm case norm. It also yields first known provably efficient approximate NN p<1. show that finds exact near neigbhor in O(log n) data satisfying certain "bounded growth" condition.Unlike schemes, our LSH works directly points Euclidean space without embeddings. Consequently, resulting query bound is free...

We study a multi-unit auction with multiple bidders, each of whom has private valuation and budget. The truthful mechanisms such an are characterized, in the sense that, under standard assumptions, we prove that it is impossible to design non-trivial which allocates all units, while provide asymptotically revenue-maximizing mechanism may allocate only some units. Our asymptotic parameter budget dominance measures size single agent relative maximum revenue. discuss relevance these results for...

We study a generalization of the classical secretary problem which we call matroid problem. In this problem, elements are presented to an online algorithm in random order. When element arrives, observes its value and must make irrevocable decision regarding whether or not accept it. The accepted form independent set, objective is maximize combined these elements. This paper presents O(log k)-competitive for general matroids (where k rank matroid), constant-competitive algorithms several...

We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their utility by equalizing return-on-investment across all keywords. show that existing auction mechanisms combined this can experience cycling (as has been observed many current systems), therefore propose modified class small random perturbations. This perturbation is reminiscent time-dependent...

Many centralized two-sided markets form a matching between participants by running stable marriage algorithm. It is well-known fact that no mechanism based on algorithm can guarantee truthfulness as dominant strategy for participants. However, we will show in this paper, probabilistic setting where the preference lists of one side market are composed only constant (independent size market) number entries, each drawn from an arbitrary distribution, have more than partner vanishingly small....

We present generalized secretary problems as a framework for online auctions. Elements, such potential employees or customers, arrive one by online. After observing the value derived from an element, but without knowing values of future elements, algorithm has to make irrevocable decision whether retain element part solution, reject it. The way in which differs traditional algorithms is that elements uniformly random order. Many natural auction scenarios can be cast problems, imposing...

We investigate the idea of finding semantically related search engine queries based on their temporal correlation; in other words, we infer that two are if popularities behave similarly over time. To this end, first define a new measure correlation coefficient frequency functions. then conduct extensive experiments using our massive query streams from MSN engine, revealing technique can discover wide range similar queries. Finally, develop method efficiently highest correlated for given...

We consider a monopolist seller with n heterogeneous items, facing single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his set ofitems is additive. aims to maximize revenue.It known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] menusof infinite size [15]. Hart Nisan [17] have initiated astudy of two very simple pricing schemes setting:item pricing, which priced at its...

When consequential decisions are informed by algorithmic input, individuals may feel compelled to alter their behavior in order gain a system's approval. Models of agent responsiveness, termed "strategic manipulation," analyze the interaction between learner and agents world where all equally able manipulate features an attempt "trick" published classifier. In cases real classification, however, agent's ability adapt algorithm is not simply function her personal interest receiving positive...

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies assignments of devices that k-fault tolerance. Specifically, we require all links established by this setting be symmetric and form a k-vertex connected subgraph the graph. problem known NP-hard. We show current heuristic approaches can use arbitrarily more than optimal solution. Hence, seek approximation algorithms for problem. present three algorithms. The...

Combinatorial optimization is often used to plan ahead, purchasing and allocating resources for demands that are not precisely known at the time of solution. This advance planning may be done because become very expensive purchase or difficult allocate last minute when known. In this work we study tradeoffs involved in making some purchase/allocation decisions early reduce cost while deferring others greater expense take advantage additional, late-arriving information. We consider a number...

In many real world applications of influence maximization, practitioners intervene in a population whose social structure is initially unknown. This poses multiagent systems challenge to act under uncertainty about how the agents are connected. We formalize this problem by introducing exploratory which an algorithm queries individual network nodes (agents) learn their links. The goal locate seed set nearly as influential global optimum using very few queries. show that intractable for...

In many settings, competing technologies -- for example, operating systems, instant messenger or document formats can be seen adopting a limited amount of compatibility with one another; in other words, the difficulty using multiple is balanced somewhere between two extremes impossibility and effortless interoperability. There are range reasons why this phenomenon occurs, which based on legal, social, business considerations seem to defy concise mathematical models. Despite this, we show...

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies assignments of devices that k-fault tolerance. Specifically, we require all links established by this setting be symmetric and form a k-vertex connected subgraph the graph. problem known NP-hard. We show current heuristic approaches can use arbitrarily more than optimal solution. Hence, seek approximation algorithms for problem. present three algorithms. The...

The classical secretary problem studies the of selecting online an element (a secretary) with maximum value in a randomly ordered sequence. difficulty lies fact that must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for problems (see, e.g., survey Freeman [7]) several variants. We study following two extensions problem:• In discounted problem, there time-dependent discount factor d(t), benefit derived from...

We revisit classic algorithmic search and optimization problems from the perspective of competition. Rather than a single optimizer minimizing expected cost, we consider zero-sum game in which problem is presented to two players, whose only goal outperform opponent. Such games are typically exponentially large games, but they often have rich structure. provide general techniques by such structure can be leveraged find minmax-optimal approximate strategies. give examples ranking, hiring,...