waashk/dblp huggingface dataset:
fast convergence of selfish rerouting. we consider n anonymous selfish users that route their communication through m parallel links. the users are allowed to reroute, concurrently, from overloaded links to underloaded links. the different rerouting decisions are concurrent, randomized and independent. the rerouting process terminates when the system reaches a nash equilibrium, in which no user can improve its state.we study the convergence rate of several migration policies. the first is a very natural policy, which balances the expected load on the links, for the case that all users are identical and apply it, we show that the rerouting terminates in expected o(log log n + log m) stages. later, we consider the nash rerouting policies class, in which every rerouting stage is a nash equilibrium and the users are greedy with respect to the next load they observe. we show a similar termination bounds for this class. we study the structural properties of the nash rerouting policies, and derive both existence result and an efficient algorithm for the case that the number of links is small. we also show that if the users have different weights then there exists a set of weights such that every nash rerouting terminates in &omega;(&radic;n) stages with high probability.
an approximation algorithm for the group steiner problem. the input in the group-steiner problem consists of an undirected connected graph with a cost function p(e) over the edges and a collection of subsets of vertices {gi}. each subset gi is called a group and the vertices in &cup; gi are called terminals. the goal is to find a minimum cost tree that contains at least one terminal from every group.we give the first combinatorial polylogarithmic ratio approximation for the problem on trees. let m denote the number of groups and s denote the number of terminals. the approximation ratio of our algorithm is o(log s &middot; log m/log log s) = o(log2n/log log n). this is an improvement by a &theta;(log log n) factor over the previously best known approximation ratio for the group steiner problem on trees [gkr98].our result carries over to the group steiner problem on general graphs and to the covering steiner problem. garg et al. [gkr98] presented a reduction of the group steiner problem on general graphs to trees. their reduction employs bartal's [b98] approximation of graph metrics by tree metrics. our algorithm on trees implies an approximation algorithm of ratio o(log s &middot; log m &middot; log n &middot; log log n/log log s) = o(log3n) for the group steiner problem on general graphs. the previously best known approximation ratio for this problem on general graphs, as a function of n, is o(log3n &middot; log log n) [gkr98]. our algorithm in conjunction with ideas of [eks01] gives an o(log s &middot; log m &middot; log n &middot; log log n/log log s) = o(log3n)-approximation ratio for the more general covering steiner problem, improving the best known approximation ratio (as a function of n) for the covering steiner problem by a &theta;(log log n) factor.
layout area of the hypercube (extended abstract). in this paper we study the square grid area required for laying out hl, the boolean hypercube of n = 2l vertices. it is shown that this area is 4/9n2 + o(n2). we describe a layout which occupies this much area and prove that no layout of less area exists.
output-sensitive construction of the union of triangles. we present an efficient algorithm for the following problem: given a collection t = {&delta;1.....,&delta;n} of n triangles in the plane, such that there exists a subset s &sub; t (unknown to us), of &cup;&delta; &isin; s &delta; = &cup;&delta;&delta;&isin;t&delta; n triangles, such that &zeta; &laquo; construct efficiently the union of the triangles in t. we show that this problem can be solved in subquadratic time. in our solution, we use the approximate disjoint-cover (dc) algorithm, presented as a heuristics in [9]. we present a detailed implementation of this method, which combines a variety of techniques related to range-searching in two dimensions. we provide a rigorous analysis of its performance in the above setting, showing that it does indeed run in subquadratic time (for a reasonable range of &zeta;).
comparing top k lists. motivated by several applications, we introduce various distance measures between "top k lists." some of these distance measures are metrics, while others are not. for each of these latter distance measures, we show that they are "almost" a metric in the following two seemingly unrelated aspects:(i) they satisfy a relaxed version of the polygonal (hence, triangle) inequality, and(ii) there is a metric with positive constant multiples that bound our measure above and below.this is not a coincidence---we show that these two notions of almost being a metric are the same. based on the second notion, we define two distance measures to be equivalent if they are bounded above and below by constant multiples of each other. we thereby identify a large and robust equivalence class of distance measures.besides the applications to the task of identifying good notions of (dis)similarity between two top k lists, our results imply polynomial-time constant-factor approximation algorithms for the rank aggregation problem with respect to a large class of distance measures.
the k-traveling repairman problem. we consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. we give an 8.497&alpha;-approximation algorithm for this generalization, where &alpha; denotes the best achievable approximation factor for the problem of finding the least cost rooted tree spanning i vertices (i-mst) problem. this can be compared with the best known approximation algorithm for the case k = 1, which is 3.59&alpha;. we are aware of no previous work on the approximability of the present problem.in addition, we give a simple proof of the 3.59&alpha;approximation result which can be extended to the case of multiple repairmen.
an improved approximation algorithm for the 0-extension problem. given a graph g = (v, e), a set of terminals t &sube; v, and a metric d on t, the 0-extension problem is to assign vertices in v to terminals, so that the sum, over all edges e, of the distance (under d) between the terminals to which the end points of e are assigned, is minimized. this problem was first studied by karzanov. calinescu, karloff and rabani gave an o(logk) approximation algorithm based on a linear programming relaxation for the problem, where k is the number of terminals. we improve on this bound, and give an o(log k/log log k) approximation algorithm for the problem.
on local register allocation. in this paper, we consider the problem of local register allocation (lra): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between cpu and the memory system. local register allocation has been studied for more than thirty years in the theory and compiler communities. it was not known if lra is np-hard, but no subexponential time algorithm was known. furthermore, the most popular heuristics in use in compilers can perform arbitrarily poorly in the worst case. in this paper, we present the following results: we show that the local register allocation problem is np-hard. we show that a variant of the furthest-first heuristic achieves a good approximation ratio. we give a 2-approximation algorithm for lra. we report the experimental performance of a branch-and-bound algorithm and both approximation algorithms on standard benchmarks.
two algorithms for general list matrix partitions. list matrix partitions are restricted binary list constraint satisfaction problems which generalize list homomorphisms and many graph partition problems arising, e.g., in the study of perfect graphs. most of the existing algorithms apply to concrete small matrices, i.e., to partitions into a small number of parts. we focus on two general classes of partition problems, provide algorithms for their solution, and discuss their implications.the first is an o(nr+2)-algorithm for the list m-partition problem where m is any r by r matrix over subsets of {0, 1}, which has the "bisplit property". this algorithm can be applied to recognize so-called k-bisplit graphs in polynomial time, yielding a solution of an open problem from [2].the second is an algorithm running in time (rn)o(log r log n/log log n)no(log2r) for the list m-partition problem where m is any r &times; r matrix over subsets of {0,1,...,q- 1}, with the "incomplete property". this algorithm applies to all non-np-complete list m-partition problems with r = 3, and it improves the running time of the quasi-polynomial algorithm for the "stubborn problem" from [5], and for the "edge-free three-coloring problem" from [12].
finding large cycles in hamiltonian graphs. we show how to find in hamiltonian graphs a cycle of length n^@w^(^1^/^l^o^g^l^o^g^n^)=exp(@w(logn/loglogn)). this is a consequence of a more general result in which we show that if g has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor h with k vertices), then we can find in o(n^3) time a cycle in g of length k^@w^(^1^/^l^o^g^d^). from this we infer that if g has a cycle of length k, then one can find in o(n^3) time a cycle of length k^@w^(^1^/^(^l^o^g^(^n^/^k^)^+^l^o^g^l^o^g^n^)^), which implies the result for hamiltonian graphs. our results improve, for some values of k and d, a recent result of gabow (2004) [11] showing that if g has a cycle of length k, then one can find in polynomial time a cycle in g of length exp(@w(logk/loglogk)). we finally show that if g has fixed euler genus g and has a cycle with k vertices (or a 3-cyclable minor h with k vertices), then we can find in polynomial time a cycle in g of length f(g)k^@w^(^1^), running in time o(n^2) for planar graphs.
web caching with request reordering. current web caching algorithms process requests in the order of the arrival. while such restriction is inevitable in system paging due to the sequential nature of a program, the http requests are (essentially) independent at a high volume proxy server. this gives a proxy server the flexibility to reorder requests, provided no request is inordinately delayed. the expectation is that reordering requests may lead to better performance. we formulate an online k-reordering problem that captures such phenomenon for unit caches. we give a dynamic programming algorithm to solve the offline case. we give o(1) upper and lower bound on the competitive ratio of the online algorithms. we also generalize this problem to any metric space.
graph distances in the streaming model: the value of space. we investigate the importance of space when solving problems based on graph distance in the streaming model. in this model, the input graph is presented as a stream of edges in an arbitrary order. the main computational restriction of the model is that we have limited space and therefore cannot store all the streamed data; we are forced to make space-efficient summaries of the data as we go along. for a graph of n vertices and m edges, we show that testing many graph properties, including connectivity (ergo any reasonable decision problem about distances) and bipartiteness, requires &omega;(n) bits of space. given this, we then investigate how the power of the model increases as we relax our space restriction. our main result is an efficient randomized algorithm that constructs a (2t + 1)-spanner in one pass. with high probability, it uses o(t .n1+1/t log2n) bits of space and processes each edge in the stream in o(t2&middot;n1/t log n) time. we find approximations to diameter and girth via the constructed spanner. for t = &omega;(log n/log log n), the space requirement of the algorithm is o(n .polylog n), and the per-edge processing time is o(polylog n). we also show a corresponding lower bound of t for the approximation ratio achievable when the space restriction is o(t.n1+1/t log2n).we then consider the scenario in which we are allowed multiple passes over the input stream. here, we investigate whether allowing these extra passes will compensate for a given space restriction. we show that finding vertices at distance d from a particular vertex will always take d passes, for all d &isin; {1,...,t/2}, when the space restriction is o(n1+1/t). for girth, we show the existence of a direct trade-off between space and passes in the form of a lower bound on the product of the space requirement and number of passes. finally, we conclude with two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by at most a log factor.
minimizing the stabbing number of matchings, trees, and triangulations. the (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. we investigate problems of finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of points. the complexity of these problems has been a long-standing open problem; in fact, it is one of the original 30 outstanding open problems in computational geometry on the list by demaine, mitchell, and o'rourke.we show that minimum stabbing problems are np-complete. we also show that an iterated rounding technique is applicable for matchings and spanning trees of minimum stabbing number by showing that there is a polynomially solvable lp-relaxation that has fractional solutions with at least one heavy edge. this suggests constant-factor approximations. our approach uses polyhedral methods that are related to another open problem (from a combinatorial optimization list), in combination with geometric properties. we also demonstrate that the resulting techniques are practical for actually solving problems with up to several hundred points optimally or near-optimally.
lp decoding achieves capacity. we give a linear programming (lp) decoder that achieves the capacity (optimal rate) of a wide range of probabilistic binary communication channels. this is the first such result for lp decoding. more generally, as far as the authors are aware this is the first known polynomial-time capacity-achieving decoder with the maximum-likelihood (ml) certificate property---where output codewords come with a proof of optimality. additionally, this result extends the capacity-achieving property of expander codes beyond the binary symmetric channel to a larger family of communication channels.perhaps most importantly, since lp decoding performs well in practice on turbo codes and low-density parity-check (ldpc) codes (comparable to the popular "belief propagation" algorithm), this result exhibits the power of a new, widely applicable "dual witness" technique (feldman, malkin, servedio, stein and wainwright, isit '04) for bounding decoder performance.for expander codes over an adversarial channel, we prove that lp decoding corrects a constant fraction of errors. to show this, we provide a new combinatorial characterization of error events that is of independent interest, and which we expect will lead to further improvements.
hamiltonicity and colorings of arrangement graphs. we study connectivity, hamilton path and hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical) arrangements. while arrangements as geometric objects are well studied in discrete and computational geometry, their graph theoretical properties seem to have received little attention so far. in this paper we show that they provide well-structured examples of families of planar and projective-planar graphs with very interesting properties. most prominently, spherical arrangements admit decompositions into two hamilton cycles; this is a new addition to the relatively few families of 4-regular graphs that are known to have hamiltonian decompositions. other classes of arrangements have interesting properties as well: 4-connectivity, 3-vertex coloring or hamilton paths and cycles. we show a number of negative results as well: there are projective arrangements which cannot be 3-vertex colored. a number of conjectures and open questions accompany our results.
an experimental study of an opportunistic index. the size of electronic data is currently growing at a faster rate than computer memory and disk storage capacities. for this reason compression appears always as an attractive choice, if not mandatory. however space overhead is not the only resource to be optimized when managing large data collections; in fact data turn out to be useful only when properly indexed to support search operations that efficiently extract the user-requested information. approaches to combine compression and indexing techniques are nowadays receiving more and more attention. a first step towards the design of a compressed full-text index achieving guaranteed performance in the worst case has been recently done in [10]. this index combines the compression algorithm proposed by burrows and wheeler [5] with the suffix array data structure [16]. the index is opportunistic in that it takes advantage of the compressibility of the input data by decreasing the space occupancy at no significant asymptotic slowdown in the query performance. in this paper we present an implementation of this index and perform an extensive set of experiments on various text collections. the experiments show that our index is compact (its space occupancy is close to the one achieved by the best known compressors), it is fast in counting the number of pattern occurrences, and the cost of their retrieval is reasonable when they are few (i.e., in case of a selective query). in addition, our experiments show that the fm-index is flexible in that it is possible to trade space occupancy for search time by choosing the amount of auxiliary information stored into it.
compression boosting in optimal linear time using the burrows-wheeler transform. in this paper we provide the first compression booster that turns a zeroth order compressor into a more effiective k-th order compressor without any loss in time efficiency. more precisely, let a be an algorithm that compresses a string s within &lambda;|s|h*0(s)+&mu; bits of storage in o(t (|s|)) time, where h*0(s) is the zeroth order entropy of the string s. our booster improves a by compressing s within &lambda;|s|h*0(s) + log2 |s| + gk bits still using o(t (|s|)) time, where h*k(s) is the k-th order entropy of s.the idea of a "compression booster" has been very recently introduced by giancarlo and sciortino in [7]. they combined the burrows-wheeler transform [3] with dynamic programming and achieved our same compression bound but with running time o(t (|s|)) + &omega;(|s|2). we start from the same premises of [7], but instead of using dynamic programming we design a linear time optimization algorithm based on novel structural properties of the burrows-wheeler transform.
making data structures confluently persistent. we address a longstanding open problem of [j.r. driscoll, n. sarnak, d. sleator, r. tarjan, j. comput. system sci. 38 (1989) 86-124, j. driscoll, d. sleator, r. tarjan, j. acm, 41 (5) (1994) 943-959], and present a general transformation that transforms any pointer based data structure to be confluently persistent. such transformations for fully persistent data structures are given in [j.r. driscoll, n. sarnak, d. sleator, r. tarjan, j. comput. system sci. 38 (1989) 86-124], greatly improving the performance compared to the naive scheme of simply copying the inputs. unlike fully persistent data structures, where both the naive scheme and the fully persistent scheme of [j.r. driscoll, n. sarnak, d. sleator, r. tarjan, j. comput. system sci. 38 (1989) 86-124] are feasible, we show that the naive scheme for confluently persistent data structures is itself infeasible (requires exponential space and time). thus, prior to this paper there was no feasible method for making any data structure confluently persistent at all. our methods give an exponential reduction in space and time compared to the naive method, placing confluently persistent data structures in the realm of possibility.
online conflict-free coloring for intervals. we consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval i there is a color that appears exactly once in i. we present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. we first show that a natural and simple (deterministic) approach may perform rather poorly, requiring &omega;(&radic;n) colors in the worst case. we then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of &theta;(log2 n) colors. next, we present two randomized solutions. the first algorithm requires an expected number of at most o(log2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most o(log n log log n) colors but always produces a valid coloring. we also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only o(log n) colors. finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. the average-case behavior for disks, and cases involving other planar ranges, are still open.
censorship resistant peer-to-peer content addressable networks. we present a censorship resistant peer-to-peer content addressable network for accessing n data items in a network of n nodes. each search for a data item in the network takes o(log n) time and requires at most o(log2n) messages. our network is censorship resistant in the sense that even after adversarial removal of an arbitrarily large constant fraction of the nodes in the network, all but an arbitrarily small fraction of the remaining nodes can obtain all but an arbitrarily small fraction of the original data items. the network can be created in a fully distributed fashion. it requires only o(log n) memory in each node. we also give a variant of our scheme that has the property that it is highly spam resistant: an adversary can take over complete control of a constant fraction of the nodes in the network and yet will still be unable to generate spam.
the number of bit comparisons used by quicksort: an average-case analysis. the analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit comparisons. on the other hand, the standard analyses of many other algorithms (such as quicksort) are performed in terms of the number of key comparisons. we introduce the prospect of a fair comparison between algorithms of the two types by providing an averagecase analysis of the number of bit comparisons required by quicksort. counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total. we also provide a new algorithm, "bitsquick", that reduces this factor to constant order by eliminating needless bit comparisons.