waashk/dblp huggingface dataset:
assignment problem in content distribution networks: unsplittable hard-capacitated facility location. in a content distribution network (cdn), there are m servers storing the data; each of them has a specific bandwidth. all the requests from a particular client should be assigned to one server, because of the routing protocol used. the goal is to minimize the total cost of these assignments ---cost of each is proportional to the distance as well as the request size--- while the load on each server is kept below its bandwidth limit. when each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem. as much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). we observe it is np-hard to approximate the cost to within any bounded factor. thus, for an arbitrary constant &epsilon; > 0, we relax the capacities to a 1 + &epsilon; factor. for the case where capacities are almost uniform, we give a bicriteria o(log n, 1 + &epsilon;)-approximation algorithm for general metrics and a (1 + &epsilon;, 1 + &epsilon;)-approximation algorithm for tree metrics. a bicriteria (&alpha;, &beta;)-approximation algorithm produces a solution of cost at most &alpha; times the optimum, while violating the capacities by no more than a &beta; factor. we can get the same guarantee for non-uniform capacities if we allow quasipolynomial running time. in our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of clients they serve. a straight-forward approach results in exponential running time. when costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation. it is worth noting that our results generalize bin packing (zero cost matrix and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all costs being zero) and some facility location problems.
the johnson-lindenstrauss lemma almost characterizes hilbert space, but not quite. let x be a normed space that satisfies the johnson-lindenstrauss lemma (j--l lemma, in short) in the sense that for any integer n and any x1,...,xn &epsilon; x there exists a linear mapping l: x &rarr; f, where f &sube; x is a linear subspace of dimension o(log n), such that ||xi - xj|| &le; ||l(xi) - l(xj)|| &le; o(1) &middot; ||xi - xj|| for all i, j &epsilon; {1,..., n). we show that this implies that x is almost euclidean in the following sense: every n-dimensional subspace of x embeds into hilbert space with distortion [equation]. on the other hand, we show that there exists a normed space y which satisfies the j-l lemma, but for every n there exists an n-dimensional subspace en &sube; y whose euclidean distortion is at least 2&omega;(&alpha;(n)), where &alpha; is the inverse ackermann function.
online scheduling to minimize the maximum delay factor. in this paper two scheduling models are addressed. first is the standard model (unicast) where requests (or jobs) are independent. the other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. we consider online scheduling of requests when they have deadlines. unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum delay factor. the delay factor of a schedule is defined to be the minimum &alpha; &ge; 1 such that each request i is completed by time ai + &alpha;(di - ai) where ai is the arrival time of request i and di is its deadline. delay factor generalizes the previously defined measure of maximum stretch which is based only the processing times of requests [9, 11]. we prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. motivated by this, we consider resource augmentation analysis [24] and prove the following positive results. for the unicast model we give algorithms that are (1 + &epsilon;)-speed o(1/&epsilon;)-competitive in both the single machine and multiple machine settings. in the broadcast model we give an algorithm for same-sized pages that is (2 + &epsilon;)-speed o(1/&epsilon;2)-competitive. for arbitrary page sizes we give an algorithm that is (4 + &epsilon;)-speed o(1/&epsilon;2)-competitive.
improved equilibria via public service advertising. many natural games have both high and low cost nash equilibria: their price of anarchy is high and yet their price of stability is low. in such cases, one could hope to move behavior from a high cost equilibrium to a low cost one by a "public service advertising campaign" encouraging players to follow the low-cost equilibrium, and if every player follows the advice then we are done. however, the assumption that everyone follows instructions is unrealistic. a more natural assumption is that some players will follow them, while other players will not. in this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. unlike the "value of altruism" model, we assume everyone will ultimately act in their own interest. we analyze this question for several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, and party affiliation games (which include consensus and cut games). we show that for some of these games (such as fair cost sharing), a random &alpha; fraction of the population following the given advice is sufficient to get a guarantee within an o(1/&alpha;) factor of the price of stability for any &alpha; > 0. for other games (such as party affiliation games), there is a strict threshold (in this case, &alpha; < 1/2 yields almost no benefit, yet &alpha; > 1/2 is enough to reach near-optimal behavior). finally, for some games, such as scheduling, no value &alpha; < 1 is sufficient. we also consider a "viral marketing" model in which certain players are specifically targeted, and analyze the ability of such targeting to influence behavior using a much smaller number of targeted players.
the geometry of binary search trees. we present a novel connection between binary search trees (bsts) and points in the plane satisfying a simple property. using this correspondence, we achieve the following results: 1. a surprisingly clean restatement in geometric terms of many results and conjectures relating to bsts and dynamic optimality. 2. a new lower bound for searching in the bst model, which subsumes the previous two known bounds of wilber [focs'86]. 3. the first proposal for dynamic optimality not based on splay trees. a natural greedy but offline algorithm was presented by lucas [1988], and independently by munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. we show that there exists an equal-cost online algorithm, transforming the conjecture of lucas and munro into the conjecture that the greedy algorithm is dynamically optimal.
improved approximating algorithms for directed steiner forest. we consider the k-directed steiner forest (k-dsf) problem: given a directed graph g = (v, e) with edge costs, a collection d &isin; v x v of ordered node pairs, and an integer k &le; |d|, find a min-cost subgraph h of g that contains an st-path for (at least) k pairs (s, t) &isin; d. when k = |d|, we get the directed steiner forest (dsf) problem. the best known approximation ratios for these problems are: &otilde;(k2/3) for k-dsf by charikar et al. [2], and o(k1/2+&epsilon;) for dsf by chekuri et al. [3]. for dsf we give an o(n&epsilon;&middot;min {n4/5,m2/3})-approximation scheme using a novel lp-relaxation seeking to connect pairs via "cheap" paths. this is the first sublinear (in terms of n = |v|) approximation ratio for the problem. for k-dsf we give a simple greedy o(k1/2+&epsilon;)-approximation scheme, improving the best known ratio &otilde;(k2/3) by charikar et al. [2], and (almost) matching, in terms of k, the best ratio known for the undirected variant [11]. even when used for the particular case dsf, our algorithm favorably compares to the one of [3], which repeatedly solves linear programs, and uses complex time and space consuming transformations.
efficient algorithms for the 2-gathering problem. pebbles are placed on some vertices of a directed graph. is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? we give an o(mn)-time algorithm for solving this problem, which we call the 2-gathering problem, where n is the number of vertices and m is the number of edges of the graph. if such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of solitary pebbles. the 2-gathering problem forms a nontrivial generalization of the nonbipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.
comparison-based time-space lower bounds for selection. we establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. we prove that any comparison-based randomized algorithm for finding the median requires &omega;(nlog logs n) expected time in the ram model (or more generally in the comparison branching program model), if we have s bits of extra space besides the read-only input array. this bound is tight for all s &gt; log n, and remains true even if the array is given in a random order. our result thus answers a 16-year-old question of munro and raman &lsqb;1996&rsqb;, and also complements recent lower bounds that are restricted to sequential access, as in the multipass streaming model &lsqb;chakrabarti et al. 2008b&rsqb;. we also prove that any comparison-based, deterministic, multipass streaming algorithm for finding the median requires &omega;(nlog&ast;(n/s)+ nlogs n) worst-case time (in scanning plus comparisons), if we have s cells of space. this bound is also tight for all s &gt;log2 n. we get deterministic lower bounds for i/o-efficient algorithms as well. the proofs in this article are self-contained and do not rely on communication complexity techniques.
finding duplicates in a data stream. given a data stream of length n over an alphabet [m] where n > m, we consider the problem of finding a duplicate in a single pass. we give a randomized algorithm for this problem that uses o((log m)3) space. this answers a question of muthukrishnan [mut05] and tarui [tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. our main tool is an isolation lemma that reduces this problem to the task of detecting and identifying a dictatorial variable in a boolean halfspace. we present various relaxations of the condition n > m, under which one can find duplicates efficiently.
approximation algorithms for restless bandit problems. in this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. in its ultimate generality, the restless bandit problem is known to be pspace-hard to approximate to any non-trivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. we make progress on this problem by showing that for an interesting and general subclass that we term monotone bandits, a surprisingly simple and intuitive greedy policy yields a factor 2 approximation. such greedy policies are termed index policies, and are popular due to their simplicity and their optimality for the stochastic multi-armed bandit problem. the monotone bandit problem strictly generalizes the stochastic multi-armed bandit problem, and naturally models multi-project scheduling where the state of a project becomes increasingly uncertain when the project is not scheduled. we develop several novel techniques in the design and analysis of the index policy. our algorithm proceeds by introducing a novel "balance" constraint to the dual of a well-known lp relaxation to the restless bandit problem. this is followed by a structural characterization of the optimal solution by using both the exact primal as well as dual complementary slackness conditions. this yields an interpretation of the dual variables as potential functions from which we derive the index policy and the associated analysis.
efficient coordination mechanisms for unrelated machine scheduling. we present three new coordination mechanisms for scheduling n selfish jobs on m unrelated machines. a coordination mechanism aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. the scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. we consider the maximum completion time among all jobs as the measure of the efficiency of schedules. the approximation ratio of a coordination mechanism quantifies the efficiency of pure nash equilibria (price of anarchy) of the induced game. our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. our first coordination mechanism has approximation ratio o(log m) and always guarantees that the induced game has pure nash equilibria to which the system converges in at most n rounds. this result improves a recent bound of o(log2 m) due to azar, jain, and mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct ids. next we study the intriguing scenario where jobs are anonymous, i.e., they have no ids. in this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. our second mechanism handles anonymous jobs and has approximation ratio o (log m/log log m) although the game induced is not a potential game and, hence, the existence of pure nash equilibria is not guaranteed by potential function arguments. however, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. our third coordination mechanism also handles anonymous jobs and has a nice "cost-revealing" potential function. besides in proving the existence of equilibria, we use this potential function in order to upper-bound the price of stability of the induced game by o(log m), the price of anarchy by o(log2 m), and the convergence time to o(log2 m)-approximate assignments by a polynomial number of best-response moves. our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.
a universally fastest algorithm for max 2-sat, max 2-csp, and everything in between. we introduce "hybrid" max 2-csp formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. this allows an algorithm to use both efficient reductions specific to and and or clauses, and other powerful reductions that require the general csp setting. parametrizing an instance by the fraction p of nonsimple clauses, we give an exact (exponential-time) algorithm that is the fastest polynomial-space algorithm known for max 2-sat (and other p = 0 formulas, with arbitrary mixtures of and and or clauses); the only efficient algorithm for mixtures of and, or, and general integer-valued clauses; and tied for fastest for general max 2-csp (p = 1). since a pure 2-sat input instance may be transformed to a general csp instance in the course of being solved, the algorithm's efficiency and generality go hand in hand. our novel analysis results in a family of running-time bounds, each optimized for a particular value of p. the algorithm uses new reductions introduced here, as well as recent reductions such as "clause-learning" and "2-reductions" adapted to our setting's mixture of simple and general clauses. each reduction imposes constraints on various parameters, and the running-time bound is an "objective function" of these parameters and p. the optimal running-time bound is obtained by solving a convex nonlinear program, which can be done efficiently and with a certificate of optimality.
(un)expected behavior of digital search tree profile. a digital search tree (dst) -- one of the most fundamental data structures on words -- is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. such trees find myriad of applications from the popular lempel-ziv'78 data compression scheme to distributed hash tables. the profile of a dst measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. most parameters of dst (e.g., height, fill-up) can be expressed in terms of the profile. however, from the inception of dst, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. we make here the first, but decisive, step towards solving this problem. we present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. the main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. we present such a solution for the poissonized version of the problem (i.e., when the number of stored strings is generated by a poisson distribution) in the mellin transform domain. to accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools to extract the asymptotic behavior of the profile. this analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. the average profile undergoes several phase transitions when moving from the root to the longest path. at first, it resembles a full tree until it abruptly starts growing polynomially and it oscillates in this range. our results are derived by methods of analytic algorithmics such as generating functions, mellin transform, poissonization and de-poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis.
3-bit dictator testing: 1 vs. 5/8. in the conclusion of his monumental paper on optimal inapproximability results, h&aring;stad [13] suggested that fourier analysis of dictator (long code) tests may not be universally applicable in the study of csps. his main open question was to determine if the technique could resolve the approximability of satisfiable 3-bit constraint satisfaction problems. in particular, he asked if the "not two" (ntw) predicate is non-approximable beyond the random assignment threshold of 5/8 on satisfiable instances. around the same time, zwick [30] showed that all satisfiable 3-csps are 5/8-approximable and conjectured that the 5/8 is optimal. in this work we show that fourier analysis techniques can produce a dictator test based on ntw with completeness 1 and soundness 5/8. our test's analysis uses the bonami-gross-beckner hypercontractive inequality. we also show a soundness lower bound of 5/8 for all 3-query dictator tests with perfect completeness. this lower bound for property testing is proved in part via a semidefinite programming algorithm of zwick [30]. our work precisely determines the 3-query "dictatorship testing gap". although this represents progress on zwick's conjecture, current pcp "outer verifier" technology is insufficient to convert our dictator test into an np-hardness-of-approximation result.
on stars and steiner stars: ii. a steiner star for a set p of n points in rd connects an arbitrary center point to all points of p, while a star connects a point p &isin; p to the remaining n -- 1 points of p. all connections are realized by straight line segments. fekete and meijer showed that the minimum star is at most &radic;2 times longer than the minimum steiner star for any finite point configuration in rd. the maximum ratio between them, over all finite point configurations in rd, is called the star steiner ratio in rd. it is conjectured that this ratio is 4/&pi; = 1.2732 ... in the plane and 4/3 = 1.3333 ... in three dimensions. here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and &radic;2--10&minus;4, respectively. our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among n points on the unit sphere, first studied by l&aacute;szl&oacute; fejes t&oacute;th. it is quite general and yields the first nontrivial estimates below &radic;2 on the star steiner ratios in arbitrary dimensions. we show, however, that the star steiner ratio in rd tends to &radic;2, the upper bound given by fekete and meijer, as d goes to infinity. our estimates on the star steiner ratios are therefore much closer to the conjectured values in higher dimensions! as it turns out, our estimates as well as the conjectured values of the steiner ratios (in the limit, for n going to infinity) are related to the classical infinite wallis product: [equation]
on the power of two, three and four probes. an adaptive (n, m, s, t)-scheme is a deterministic scheme for encoding a vector x of m bits with at most n ones by a vector y of s bits, so that any bit of x can be determined by t adaptive probes to y. a non-adaptive (n, m, s, t)-scheme is defined analogously. the study of such schemes arises in the investigation of the static membership problem in the bitprobe model. answering a question of buhrman, miltersen, radhakrishnan and venkatesh [sicomp 2002] we present adaptive (n, m, s, 2) schemes with s < m for all n satisfying 4n2 + 4n < m and adaptive (n, m, s, 2) schemes with s = o(m) for all n = o(log m). we further show that there are adaptive (n, m, s, 3)-schemes with s = o(m) for all n = o(m), settling a problem of radhakrishnan, raman and rao [esa 2001], and prove that there are non-adaptive (n, m, s, 4)-schemes with s = o(m) for all n = o(m). therefore, three adaptive probes or four non-adaptive probes already suffice to obtain a significant saving in space compared to the total length of the input vector. lower bounds are discussed as well.