waashk/dblp huggingface dataset:
compressed representations of sequences and full-text indexes. given a sequence s &equals; s1s2&hellip;sn of integers smaller than r &equals; o(polylog(n)), we show how s can be represented using nh0(s) &plus; o(n) bits, so that we can know any sq, as well as answer rank and select queries on s, in constant time. h0(s) is the zero-order empirical entropy of s and nh0(s) provides an information-theoretic lower bound to the bit storage of any sequence s via a fixed encoding of its symbols. this extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in o(log r) time. for larger r, we can still represent s in nh0(s) &plus; o(n log r) bits and answer queries in o(log r/log log n) time. another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet &sigma;. specifically, we design a variant of the fm-index that indexes a string t[1, n] within nhk(t) &plus; o(n) bits of storage, where hk(t) is the kth-order empirical entropy of t. this space bound holds simultaneously for all k &le; &alpha; log&verbar;&sigma;&verbar; n, constant 0 < &alpha; < 1, and &verbar;&sigma;&verbar; &equals; o(polylog(n)). this index counts the occurrences of an arbitrary pattern p[1, p] as a substring of t in o(p) time; it locates each pattern occurrence in o(log1&plus;&epsiv; n) time for any constant 0 < &epsiv; < 1; and reports a text substring of length &ell; in o(&ell; &plus; log1&plus;&epsiv; n) time. compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. still, our index uses essentially the same space of the kth-order entropy of the text t, which is the best space obtained in previous work. we can also handle larger alphabets of size &verbar;&sigma;&verbar; &equals; o(n&beta;), for any 0 < &beta; < 1, by paying o(n log&verbar;&sigma;&verbar;) extra space and multiplying all query times by o(log &verbar;&sigma;&verbar;/log log n).
nearest-neighbor-preserving embeddings. in this article we introduce the notion of nearest-neighbor-preserving embeddings. these are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. we give two examples of such embeddings for euclidean metrics with low &ldquo;intrinsic&rdquo; dimension. combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.
phase changes in random point quadtrees. we show that a wide class of linear cost measures (such as the number of leaves) in random d-dimensional point quadtrees undergo a change in limit laws: if the dimension d &equals; 1, &hellip;, 8, then the limit law is normal; if d &ge; 9 then there is no convergence to a fixed limit law. stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. our approach is new and very general, and also applicable to other classes of search trees. a brief discussion of devroye's grid trees (covering m-ary search trees and quadtrees as special cases) is given. we also propose an efficient numerical procedure for computing the constants involved to high precision.
an algorithm for deciding zero equivalence of nested polynomially recurrent sequences. we introduce the class of nested polynomially recurrent sequences which includes a large number of sequences that are of combinatorial interest. we present an algorithm for deciding zero equivalence of these sequences, thereby providing a new algorithm for proving identities among combinatorial sequences: in order to prove an identity, decide by the algorithm whether the difference of lefthand-side and righthand-side is identically zero. this algorithm is able to treat mathematical objects which are not covered by any other known symbolic method for proving combinatorial identities. despite its theoretical flavor and high complexity, an implementation of the algorithm can be successfully applied to nontrivial examples.
windows scheduling as a restricted version of bin packing. given is a sequence of n positive integers w1,w2,&hellip;,wn that are associated with the items 1,2,&hellip;n, respectively. in the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most wi slots (a slot is the transmission time of one page). in the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/wi. the optimization objective is to minimize the number of channels or bins. in the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. since a page requires at least 1/wi of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing. let h &equals; &lceil;&sumi&equals;1n(1/wi) be the bandwidth lower bound on the required number of bins (channels). the best-known offline algorithm for the windows scheduling problem used h &plus; o(ln h) channels. this article presents an offline algorithm for the unit-fractions bin packing problem with at most h &plus; 1 bins. in the online setting, this article presents algorithms for both problems with h &plus; o(&sqrt;h) channels or bins, where the one for the unit-fractions bin packing problem is simpler. on the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least h&plus;&omega(ln h) bins. for instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. finally, this article includes a new np-hardness proof for the windows scheduling problem.
multicommodity demand flow in a tree and packing integer programs. we consider requests for capacity in a given tree network t &equals; (v, e) where each edge e of the tree has some integer capacity ue. each request f is a node pair with an integer demand df and a profit wf which is obtained if the request is satisfied. the objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. this generalizes well-known problems, including the knapsack and b-matching problems. when all demands are 1, we have the integer multicommodity flow problem. garg et al. [1997] had shown that this problem is np-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. we then consider the problem with arbitrary demands. when the maximum demand dmax is at most the minimum edge capacity umin, we show that the integrality gap of the lp is at most 48. this result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. we use techniques of kolliopoulos and stein [2004, 2001] to obtain this. we also obtain, via this method, improved algorithms for line and ring networks. applications and connections to other combinatorial problems are discussed.
multiplierless multiple constant multiplication. a variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. the generation of a multiplier block from the set of constants is known as the multiple constant multiplication (mcm) problem. finding the optimal solution, namely, the one with the fewest number of additions and subtractions, is known to be np-complete. we propose a new algorithm for the mcm problem, which produces solutions that require up to 20&percnt; less additions and subtractions than the best previously known algorithm. at the same time our algorithm, in contrast to the closest competing algorithm, is not limited by the constant bitwidths. we present our algorithm using a unifying formal framework for the best, graph-based mcm algorithms and provide a detailed runtime analysis and experimental evaluation. we show that our algorithm can handle problem sizes as large as 100 32-bit constants in a time acceptable for most applications. the implementation of the new algorithm is available at www.spiral.net.
retroactive data structures. we introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. in this new paradigm, called retroactive data structures, the historical sequence of operations performed on the data structure is not fixed. the data structure allows arbitrary insertion and deletion of operations at arbitrary times, subject only to consistency requirements. we initiate the study of retroactive data structures by formally defining the model and its variants. we prove that, unlike persistence, efficient retroactivity is not always achievable. thus, we present efficient retroactive data structures for queues, doubly ended queues, priority queues, union-find, and decomposable search structures.
strongly stable matchings in time () and extension to the hospitals-residents problem. an instance of the stable marriage problem is an undirected bipartite graph g &equals; (x &cup; w, e) with linearly ordered adjacency lists with ties allowed in the ordering. a matching m is a set of edges, no two of which share an endpoint. an edge e &equals; (a, b) &isin; e&setmn; m is a blocking edge for m if a is either unmatched or strictly prefers b to its partner in m, and b is unmatched, strictly prefers a to its partner in m, or is indifferent between them. a matching is strongly stable if there is no blocking edge with respect to it. we give an o(nm) algorithm for computing strongly stable matchings, where n is the number of vertices and m the number of edges. the previous best algorithm had running time o(m2). we also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. we give an o(m &sum;h&isin;hph) algorithm for computing a strongly stable matching in the hospitals-residents problem, where ph is the quota of a hospital h. the previous best algorithm had running time o(m2).
novel architectures for p2p applications: the continuous-discrete approach. we propose a new approach for constructing p2p networks based on a dynamic decomposition of a continuous space into cells corresponding to servers. we demonstrate the power of this approach by suggesting two new p2p architectures and various algorithms for them. the first serves as a dht (distributed hash table) and the other is a dynamic expander network. the dht network, which we call distance halving, allows logarithmic routing and load while preserving constant degrees. it offers an optimal tradeoff between degree and path length in the sense that degree d guarantees a path length of o(logd n). another advantage over previous constructions is its relative simplicity. a major new contribution of this construction is a dynamic caching technique that maintains low load and storage, even under the occurrence of hot spots. our second construction builds a network that is guaranteed to be an expander. the resulting topologies are simple to maintain and implement. their simplicity makes it easy to modify and add protocols. a small variation yields a dht which is robust against random byzantine faults. finally we show that, using our approach, it is possible to construct any family of constant degree graphs in a dynamic environment, though with worse parameters. therefore, we expect that more distributed data structures could be designed and implemented in a dynamic environment.
convergence time to nash equilibrium in load balancing. we study the number of steps required to reach a pure nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. we consider a variety of load balancing models, including identical, restricted, related, and unrelated machines. our results have a crucial dependence on the weights assigned to jobs. we consider arbitrary weights, integer weights, k distinct weights, and identical (unit) weights. we look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (e.g., allowing the largest weight job to move first). a by-product of our results is establishing a connection between various scheduling models and the game-theoretic notion of potential games. we show that load balancing in unrelated machines is a generalized ordinal potential game, load balancing in related machines is a weighted potential game, and load balancing in related machines and unit weight jobs is an exact potential game.
the relative worst order ratio for online algorithms. we define a new measure for the quality of online algorithms, the relative worst order ratio, using ideas from the max/max ratio [ben-david and borodin 1994] and from the random order ratio [kenyon 1996]. the new ratio is used to compare online algorithms directly by taking the ratio of their performances on their respective worst permutations of a worst-case sequence. two variants of the bin packing problem are considered: the classical bin packing problem, where the goal is to fit all items in as few bins as possible, and the dual bin packing problem, which is the problem of maximizing the number of items packed in a fixed number of bins. several known algorithms are compared using this new measure, and a new, simple variant of first-fit is proposed for dual bin packing. many of our results are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but new separations and easier proofs are found.
faster algorithms for sorting by transpositions and sorting by block interchanges. in this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. the existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity o(n3/2 &sqrt;logn). by means of the permutation tree, we can improve this algorithm to achieve time complexity o(nlogn). we can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from o(n2) down to o(nlogn).
improved algorithms for weakly chordal graphs. we use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. for the recognition problem, we reduce the time complexity from o(mn2) to o(m2) and the space complexity from o(n3) to o(m &plus; n), and also produce a hole or antihole if the input graph is not weakly chordal. for the optimization problems, the complexity of the clique and coloring problems is reduced from o(mn2) to o(n3) and the complexity of the independent set and clique cover problems is improved from o(n4) to o(mn). the space complexity of our optimization algorithms is o(m &plus; n).
routing and scheduling in multihop wireless networks with time-varying channels. we study routing and scheduling in multihop wireless networks. when data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. the data transmission is node constrained, that is, every node can transmit data to at most one neighboring node per time step. the transmission rates are time varying as a result of changing wireless channel conditions. in this article, we assume that data arrivals and transmission rates are governed by an adversary. the power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. the node-constrained transmission and time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks. for the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. these algorithms try to give priority to the data that is closest to its source node. however, at each time step only a subset of the data queued at a node is eligible for scheduling. one of our algorithms is fully distributed. for the case in which the adversary does not dictate the data paths, we show how to route data so that the admissibility condition is satisfied. we can then schedule data along the chosen paths using our stable scheduling algorithms.
deterministic sampling and range counting in geometric data streams. we present memory-efficient deterministic algorithms for constructing &epsi;-nets and &epsi;-approximations of streams of geometric data. unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. we show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. we use these techniques to approximate several robust statistics of geometric data streams, including tukey depth, simplicial depth, regression depth, the thiel-sen estimator, and the least median of squares. our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. we also include a lower bound for noniceberg geometric queries.
constructing pairwise disjoint paths with few links. let p be a simple polygon and let &lcub;(u1, u&prime;1), (u2, u&prime;2),&hellip;,(um, u&prime;m)&rcub; be a set of m pairs of distinct vertices of p, where for every distinct i, j &le; m, there exist pairwise disjoint (nonintersecting) paths connecting ui to u&prime;i and uj to u&prime;j. we wish to construct m pairwise disjoint paths in the interior of p connecting ui to u&prime;i for i &equals; 1, &hellip;,m, with a minimal total number of line segments. we give an approximation algorithm that constructs such a set of paths using o(m) line segments in o(n log m &plus; m log m) time, where m is the number of line segments in the optimal solution and n is the size of the polygon.
approximate parameterized matching. two equal length strings s and s&prime;, over alphabets &sigma;s and &sigma;s&prime;, parameterize match if there exists a bijection &pi; : &sigma;s &rightarrow; &sigma;s&prime; such that &pi; (s) &equals; s&prime;, where &pi; (s) is the renaming of each character of s via &pi;. parameterized matching is the problem of finding all parameterized matches of a pattern string p in a text t, and approximate parameterized matching is the problem of finding at each location a bijection &pi; that maximizes the number of characters that are mapped from p to the appropriate &verbar;p&verbar;-length substring of t. parameterized matching was introduced as a model for software duplication detection in software maintenance systems and also has applications in image processing and computational biology. for example, approximate parameterized matching models image searching with variable color maps in the presence of errors. we consider the problem for which an error threshold, k, is given, and the goal is to find all locations in t for which there exists a bijection &pi; which maps p into the appropriate &verbar;p&verbar;-length substring of t with at most k mismatched mapped elements. our main result is an algorithm for this problem with o(nk1.5 &plus; mk log m) time complexity, where m &equals; &verbar;p&verbar; and n&equals;&verbar;t&verbar;. we also show that when &verbar;p&verbar; &equals; &verbar;t&verbar; &equals; m, the problem is equivalent to the maximum matching problem on graphs, yielding a o(m &plus; k1.5) solution.
the np-completeness column: finding needles in haystacks. this is the 26th edition of a column that covers new developments in the theory of np-completeness. the presentation is modeled on that which m. r. garey and i used in our book &ldquo;computers and intractability: a guide to the theory of np-completeness,&rdquo; w. h. freeman & co., new york, 1979, hereinafter referred to as &ldquo;[g&j].&rdquo; previous columns, the first 23 of which appeared in j. algorithms, will be referred to by a combination of their sequence number and year of appearance, e.g., &ldquo;column 1 [1981].&rdquo; full bibliographic details on the previous columns, as well as downloadable unofficial versions of them, can be found at http://www.research.att.com/&sim;dsj/columns/. this column discusses the question of whether finding an object can be computationally difficult even when we know that the object exists.
energy-efficient algorithms for flow time minimization. we study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. while most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. more specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. we first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. therefore, most of the article is concerned with unit-size jobs. we devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.
skip graphs. skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. they are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. in addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors within it introduced due to node failures.
finding the shortest simple paths: a new algorithm and its implementation. we describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. our algorithm is based on a replacement paths algorithm proposed by hershberger and suri [2001], and can yield a factor &theta;(n) improvement for this problem. but there is a caveat: the fast replacement paths subroutine is known to fail for some directed graphs. however, the failure is easily detected, and so our k shortest paths algorithm optimistically uses the fast subroutine, then switches to a slower but correct algorithm if a failure is detected. thus, the algorithm achieves its &theta;(n) speed advantage only when the optimism is justified. our empirical results show that the replacement paths failure is a rare phenomenon, and the new algorithm outperforms the current best algorithms; the improvement can be substantial in large graphs. for instance, on gis map data with about 5,000 nodes and 12,000 edges, our algorithm is 4--8 times faster. in synthetic graphs modeling wireless ad hoc networks, our algorithm is about 20 times faster.