We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after introduction) among practitioners, and order suggest improvements application. propose justify a clusterability criterion sets. present that quickly lead provably near-optimal solutions when applied well-clusterable instances. This is the first performance guarantee variant heuristic. The provision on output quality does not come at expense speed:...

We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where nodes may both issue requests objects and have capacity storing so as to minimize average data-access cost. introduce placement model this problem. a set caches $\mathcal{F}$, clients $\mathcal{D}$, $\mathcal{O}$. Each cache i can store at most $u_i$ objects. client $j\in\mathcal{D}$ has demand $d_j$ specific object $o(j)\in\mathcal{O}$ be assigned that stores object. Storing an o...

We give a general technique to obtain approximation mechanisms that are truthful in expectation. show for packing domains, any /spl alpha/-approximation algorithm also bounds the integrality gap of IF relaxation problem by can be used construct an mechanism is This immediately yields variety new and significantly improved results various domains furthermore, (in expectation) with guarantees match best known when truthfulness not required. In particular, we first multi-parameter domains....

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after introduction) among practitioners, and order suggest improvements application. propose justify a clusterability criterion sets. present that quickly lead provably near-optimal solutions when applied well-clusterable instances. This is the first performance guarantee variant heuristic. The provision on output quality does not come at expense speed:...

We give a general technique to obtain approximation mechanisms that are truthful in expectation. show for packing domains, any α -approximation algorithm also bounds the integrality gap of LP relaxation problem by can be used construct an mechanism is This immediately yields variety new and significantly improved results various domains furthermore, (in expectation) with guarantees match best-known when truthfulness not required. In particular, we first multiparameter domains. achieving O (√...

We consider the Correlation Clustering problem introduced in [2]. Given a graph G = (V,E) where each edge is labeled either + (similar) or - (different), we want to cluster nodes so that edges lie within clusters and -- between clusters. Specifically, maximize agreements --- number of This NP-Hard give 0.7666-approximation algorithm for maximizing on any even when have non-negative weights (along with labels) weight agreements. These were posed as open problems Previously only results known...

Stochastic optimization problems attempt to model uncertainty in the data by assuming that input is specified a probability distribution. We consider well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) one commits on initial actions, and then once actual realized (according distribution), further (recourse) actions can be taken. show for broad class linear recourse, can, any ϵ > 0, time polynomial 1/ϵ size input, compute...

We study the optimization problem faced by a perfectly informed principal in Bayesian game, who reveals information to players about state of nature obtain desirable equilibrium. This signaling is natural design question motivated uncertainty games and has attracted much recent attention. present new hardness results for problems (a) two-player zero-sum games, (b) network routing games.

Stochastic optimization problems attempt to model uncertainty in the data by assuming that (part of) input is specified terms of a probability distribution. We consider well-studied paradigm 2-stage models with recourse: first, given only distributional information about (some one commits on initial actions, and then once actual realized (according distribution), further (recourse) actions can be taken. give first approximation algorithms for discrete stochastic recourse which underlying...

We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has requirement that r distinct facilities serve it, instead just one. give 2.076-approximation algorithm for this problem using LP rounding, which is currently best-known performance guarantee. Our exploits primal and dual complementary slackness conditions based on clustered randomized rounding . A technical difficulty we overcome presence terms with negative...

We consider the problem of makespan minimization on m unrelated machines in context algorithmic mechanism design, where are strategic players. This is a multidimensional scheduling domain, and only known positive results for such domain O(m)-approximation truthful mechanisms [22, 20]. study well-motivated special case this problem, processing time job each machine may either be "low" or "high", low high values public job-dependent. preserves multidimensionality generalizes...

We define a new class of network design problems motivated by designing information networks. In our model, the cost transporting flow for set users (or servicing them facility) depends on amount requested users. assume that aggregation follows economies scale, is, incremental user is less if already served larger. Naturally, some sets might aggregate better than others, so now function actual not just their total demand.We provide constant-factor approximation algorithms to two important in...

Uncertainty is a facet of many decision environments and might arise for various reasons, such as unpredictable information revealed in the future, or inherent fluctuations caused by noise. Stochastic optimization provides means to handle uncertainty modeling it probability distribution over possible realizations actual data, called scenarios. The field stochastic optimization, programming, has its roots work Dantzig [4] Beale [1] 1950s, since increasingly found application wide variety...

It is well known that in a network with arbitrary (convex) latency functions are function of edge traffic, the worst-case ratio, over all inputs, system delay caused due to selfish behavior versus optimal centralized solution may be unbounded even if consists only two parallel links. This ratio called price anarchy (PoA). In this paper, we investigate ways by which one can reduce performance degradation behavior. We primary methods (a) Stackelberg routing strategies, where central authority,...

We consider the problem of selecting threshold times to transition a device low-power sleep states during an idle period. The two-state case in which there is single active and state continuous version ski-rental problem. generalized more than one state, each with its own power consumption rate costs. give algorithm that, given system, produces deterministic strategy whose competitive ratio arbitrarily close optimal. also produce optimal online system probability distribution that generates...

We consider the problem of selecting threshold times to transition a device low-power sleep states during an idle period. The two-state case, in which there is single active and state, continuous version ski-rental problem. generalized more than one each with its own power-consumption rate costs. give algorithm that, given system, produces deterministic strategy whose competitive ratio arbitrarily close optimal. also produce optimal online system probability distribution that generates...

We present the first polynomial-time approximation algorithms for single-minded envy-free profit-maximization problems (Guruswami et al., 2005) with limited supply. Our return a pricing scheme and subset of customers that are designated winners, which satisfy envy-freeness constraint, whereas in our analyses, we compare profit solution against optimal value corresponding social-welfare-maximization (SWM) problem finding winner-set maximum total value. take any LP-based alpha-approximation...

It is well known that in a network with arbitrary (convex) latency functions are function of edge traffic, the worst-case ratio, over all inputs, system delay caused due to selfish behavior versus optimal centralized solution may be unbounded even if consists only two parallel links. This ratio called price anarchy (PoA). In this article, we investigate ways by which one can reduce performance degradation behavior. We primary methods (a) Stackelberg routing strategies , where central...

In the $k$-committee election problem, we wish to aggregate preferences of $n$ agents over a set alternatives and select committee $k$ that minimizes cost incurred by agents. While typically assume agent are captured cardinal utility function, in many contexts only have access ordinal information, namely agents' rankings outcomes. As preference not as expressive utilities, loss efficiency is inevitable, quantified notion \emph{distortion}. We study problem electing sum $\ell$-largest costs...

In the k-committee election problem, we wish to aggregate preferences of n agents over a set alternatives and select committee k that minimizes cost incurred by agents. While typically assume agent are captured cardinal utility function, in many contexts only have access ordinal information, namely agents' rankings outcomes. As preference not as expressive utilities, loss efficiency is inevitable, quantified notion distortion. We study problem electing sum \ell-largest costs agents, when...

Stochastic optimization problems provide a means to model uncertainty in the input data where is modeled by probability distribution over possible realizations of actual data. We consider broad class these which realized revealed through series stages, and hence are called multi-stage stochastic programming problems. Our main result give first fully polynomial approximation scheme for linear with any constant number stages. The algorithm analyzed, known as sample average (SAA) method, quite...