waashk/dblp huggingface dataset:
inplace run-length 2d compressed search. the recent explosion in the amount of stored data has necessitated the storage and transmission of data in compressed form. the need to quickly access this data has given rise to a new paradigm in searching, that of compressed matching (proc. data compression conf, snow bird, ut, 1992, pp. 279-288; proc. 8th annu. symp. on combinatorial pattern matching (cpm 97), lecture notes in computer science, vol. 1264, springer, berlin, 1997, pp. 40-51; proc. 7th annu. symp. on combinatorial pattern matching (cpm 96), lecture notes in computer science, vol. 1075, springer, berlin, 1996, pp. 39-49). the goal of the compressed pattern matching problem is to find a pattern in a text without decompressing the text.the criterion of extra space is very relevant to compressed searching. an algorithm is called inplace if the amount of extra space used is proportional to the input size of the pattern. in this paper we present a 2d compressed matching algorithm that is inplace. let compressed(t) and compressed(p) denote the compressed text and pattern, respectively. the algorithm presented in this paper runs in time o(|compressed(t)| + |p|log σ) where σ is min(|p|,|σ), and σ is the alphabet, for all patterns that have no trivial rows (rows consisting of a single repeating symbol). the amount of space used is o(|compressed(p)|). the compression used is the 2d run-length compression, used in fax transmission.
optimal parallel sorting in multi-level storage. we adapt the sharesort algorithm of cypher and plaxton to run on various parallel models of multi-level storage, and analyze its resulting performance. sharesort was originally defined in the context of sorting n records on an n-processor hypercubic network. in that context, it is not known whether sharesort is asymptotically optimal. nonetheless, we find that sharesort achieves optimal time bounds for parallel sorting in multi-level storage, under a variety of models that have been defined in the literature.
inplace 2d matching in compressed images. the compressed matching problem is the problem of finding all occurrences of a pattern in a compressed text. in this paper we discuss the 2-dimensional compressed matching problem in lempel-ziv compressed images. given a pattern p of (uncompressed) size m × m, and a text t of (uncompressed) size n × n, both in 2d-lz compressed form, our algorithm finds all occurrences of p in t. the algorithm is strongly inplace, that is, the amount of extra space used is proportional to the best possible compression of a pattern of size m2. the best compression that the 2d-lz technique can obtain for a file of size m2 is o(m). the time for performing the search is o(n2) and the preprocessing time is o(m3). our algorithm is general in the sense that it can be used for any 2d compression which can be sequentially decompressed in small space.
fault-tolerant gathering algorithms for autonomous mobile robots. this paper studies fault tolerant algorithms for the problem of gathering n autonomous mobile robots. a gathering algorithm, executed independently by each robot, must ensure that all robots are gathered at one point within finite time. it is first observed that most existing algorithms fail to operate correctly in a setting allowing crash failures. subsequently, an algorithm tolerant against one crash-faulty robot in a system of three or more robots is presented. it is then shown that in an asynchronous environment it is impossible to perform a successful gathering in a 3-robot system with one byzantine failure. finally, in a fully synchronous system, an algorithm is provided for gathering n &ge; 3 robots with at most a single faulty robot, and a more general gathering algorithm is given in an n-robot system with up to f faults, where n &ge; 3 f +1.
coloring powers of planar graphs. we give nontrivial bounds for the inductiveness or degeneracy of power graphs gk of a planar graph g. this implies bounds for the chromatic number as well, since the inductiveness naturally relates to a greedy algorithm for vertex-coloring the given graph. the inductiveness moreover yields bounds for the choosability of the graph. we show that the inductiveness of a square of a planar graph g is at most $\lceil 9\delta /5 \rceil$, for the maximum degree $\delta$ sufficiently large, and that it is sharp. in general, we show for a fixed integer $k\geq1$ the inductiveness, the chromatic number, and the choosability of gk to be $o(\delta^{\lfloor k/2 \rfloor})$, which is tight.
on colorings of squares of outerplanar graphs. we investigate the clique number, the chromatic number and the inductiveness (or the degeneracy) of the square g2 of an outerplanar graph g, and bound as a function of the maximum degree &delta; of g. our main result is a tight bound of &delta; for the inductiveness of the square of any outerplanar graph g, when &delta; &ge; &tau;. this implies that a greedy algorithm yields an optimal coloring of such square graphs, and leads to an exact linear time algorithm that holds for any &delta;. we then derive optimal upper bounds on the three parameters for outerplanar graphs of smaller degree &delta; < &tau;, and in the case of chordal outerplanar graphs, classify exactly which graphs have parameters exceeding the absolute minimum. a co-product of the study is a characterization of all strongly simplicial elimination orderings of an arbitrary power of a tree.
random lifts of graphs. we describe here a simple probabilistic model for graphs that are lifts of a fixed base graph g, i.e., those graphs from which there is a covering man onto g. our aim is to investigate the properties of typical graphs in this class. in particular, we show that almost every lift of g is &dgr;(g)-connected where &dgr;(g) is the minimal degree of g. we calculate the typical edge expansion of lifts of the bouquet bd and
counting networks with arbitrary fan-out. it is shown that an acyclic smoothing network (and hence counting network) with fan-out n cannot be constructed from balancers of fan-out b1,..., bk, if there exists a prime factor p of n, such that p does not divide bi, for all i, 1 ≤ i ≤ k. this holds regardless of the depth, fan-in or size of the network, as long as they are finite. on the positive side, a simple construction of cyclic counting networks with fan-out n, for arbitrary n, is presented. an acyclic counting network with fan-in and fan-out p2k, for any integer k ≥ 0, is constructed out of 2-balancers and p-balancers.
a computational study of external-memory bfs algorithms. breadth first search (bfs) traversal is an archetype for many important graph problems. however, computing a bfs level decomposition for massive graphs was considered nonviable so far, because of the large number of i/os it incurs. this paper presents the first experimental evaluation of recent external-memory bfs algorithms for general graphs. with our stxxl based implementations exploiting pipelining and disk-parallelism, we were able to compute the bfs level decomposition of a web-crawl based graph of around 130 million nodes and 1.4 billion edges in less than 4 hours using single disk and 2.3 hours using 4 disks. we demonstrate that some rather simple external-memory algorithms perform significantly better (minutes as compared to hours) than internal-memory bfs, even if more than half of the input resides internally.
on distance scales, embeddings, and efficient relaxations of the cut cone. a central open problem in the field of finite metric spaces is to find an efficient relaxation of the cut cone---the collection of positive linear combinations of cut pseudo-metrics on a finite set. in particular, it has been asked how well squared-euclidean metrics (the so-called metrics of "negative type") embed into l1, and it is known that the answer to this question coincides with the integrality gap of a folklore semi-definite relaxation for computing the sparsest cut of a graph.bourgain's classical embedding theorem implies that any n-point metric space embeds into l2 with o(log n) distortion. we give the first embeddings for metrics of negative type which beat bourgain's bound. specifically, we show that for every &isin; > 0, there exists a &delta; > 0 such that every n-point metric of negative type embeds into l2+&isin;, with distortion o(log n)1-&delta;. we also exhibit the first o(log n) bounds on the euclidean distortion of finite subsets of lp, for 1 < p < 2. these spaces naturally interpolate between l1 and l2, and thus provide a necessary first step in resolving the long-standing open question on the euclidean distortion of finite subsets of l1.in proving these results, we introduce a number of new techniques for the construction of low-distortion embeddings. these include a generic gluing lemma which avoids the overhead that typically arises from the na&iuml;ve concatenation of different scales, and which provides new insights into the cut structure of finite graphs. we also exhibit the utility of lipschitz extension theorems from functional analysis to the embedding of finite metric spaces. finally, we prove the "big core" theorem---a significantly improved and quantitatively optimal version of the main structural theorem in [arv04] about random projections. the latter result offers a simplified hyperplane rounding algorithm for the computation of an o(&radic;logn)-approximation to the sparsest cut problem with uniform demands.
on the number of plane graphs. we investigate the number of plane geometric, i.e., straight-line, graphs, a set s of n points in the plane admits. we show that the number of plane graphs and connected plane graphs as well as the number of cycle-free plane graphs is minimized when s is in convex position. moreover, these results hold for all these graphs with an arbitrary but fixed number of edges. consequently, we provide simple proofs that the number of spanning trees, cycle-free graphs (forests), perfect matchings, and spanning paths is also minimized for point sets in convex position.in addition we construct a new extremal configuration, the so-called double zig-zag chain. most noteworthy this example bears &theta;*(&radic;72n) = &theta;*(8.4853n) triangulations and &theta;*(41.1889n) plane graphs (omitting polynomial factors in both cases), improving the previously known best maximizing examples.
competitive queueing policies for qos switches. we consider packet scheduling in a network providing differentiated services, where each packet is assigned a value. we study various queueing models for supporting qos (quality of service). in the nonpreemptive model, packets accepted to the queue will be transmitted eventually and cannot be dropped. the fifo preemptive model allows packets accepted to the queue to be preempted (dropped) prior to their departure, while ensuring that transmitted packets are sent in the order of arrival. in the bounded delay model, packets must be transmitted before a certain deadline, otherwise it is lost (while transmission ordering is allowed to be arbitrary). in all models the goal of the buffer policy is to maximize the total value of the accepted packets.let &alpha; be the ratio between the maximal and minimal value. for the non-preemptive model we derive a &theta;(log &alpha) competitive ratio, both exhibiting a buffer policy and a general lower bound. for the interesting case of two distinct values, we give an 2&alpha;--1/&alpha; competitive buffer policy, which exactly matches the lower bound. we also analyze a red-like policy and derive its competitive ratio, which is approximately 2&alpha;--0.5/&alpha; for two values and &theta;(log &alpha;) for multiple values. in addition we improve the previous known lower and upper bounds of the fixed partition and flexible partition policies.for the fifo preemptive model, we improve the general lower bound and show a tight bound for the special case of queue size 2. we prove that the bounded delay model with uniform delay 2 is equivalent to a modified fifo preemptive model with queue size 2. we then give improved upper and lower bounds on the 2-uniform bounded delay model. we also give lower bound for the 2-variable bounded delay model, which matches the previously known upper bound.
on-line scheduling of a single machine to minimize total weighted completion time. this paper considers the on-line scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. the goal is to minimize the total weighted completion time. we show that a simple modification of the shortest weighted processing time rule has a competitive ratio of 2. this result is established using a new proof technique which does not rely explicitly on a lower bound on the optimal objective function value. since it is known that no on-line algorithm can have a competitive ratio of less than 2, we have resolved the open issue of determining the minimum competitive ratio for this problem.
dynamic routing on networks with fixed-size buffers. the combination of the buffer size of routers deployed in the internet and the internet traffic itself leads routinely to routers dropping packets. motivated by this, we initiate the rigorous study of dynamic store-and-forward routing on arbitrary networks in a model in which dropped packets must explicitly be taken into account. to avoid the uncertainties of traffic modeling, we consider arbitrary traffic on the network. we analyze and compare the effectiveness of several greedy, on-line, local-control protocols using a competitive analysis of the throughput. one goal of our approach is for the competitive results to continue to hold as a network grows without requiring the memory in the nodes to increase with the size of the network. thus, in our model, we have link buffers of fixed size, b, which is independent of the size of the network, and b becomes a parameter of the model.our results are in contrast to another adversarial traffic model known as adversarial queuing theory (aqt), which studies the stability and growth rate of queues as a function of the network and traffic parameters. for example, in aqt the furthest-to-go (ftg) protocol is stable for all networks whereas nearest-to-go (ntg) can be unstable for some networks. unlike aqt, in our setting ntg is preferable to ftg: we show that the ntg protocol is throughput-competitive on all networks whereas the ftg protocol has unbounded competitiveness whenever a network contains even small cycles.
the inverse nearest neighbor problem with astrophysical applications. this paper discusses algorithmic improvements to mature astrophysics applications as part of an on-going collaboration with astrophysicists. we present an efficient algorithm for a variation of the inverse nearest neighbor problem which is a basic computation in an astrophysical n-body simulation. we obtain empirical results demonstrating the improvements, which our algorithm offers to large-scale astrophysical simulations.
improved randomized on-line algorithms for the list update problem. the best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of $\sqrt{3} \approx 1.73$. in this paper we present a new family of randomized on-line algorithms that beat this competitive ratio. our improved algorithms are called timestamp algorithms and achieve a competitiveness of $\max\{2-p, 1+p(2-p)\}$, for any real number $p\in[0,1]$. setting $p = (3-\sqrt{5})/2$, we obtain a $\phi$-competitive algorithm, where $\phi = (1+\sqrt{5})/2\approx 1.62$ is the golden ratio. timestamp algorithms coordinate the movements of items using some information on past requests. we can reduce the required information at the expense of increasing the competitive ratio. we present a very simple version of the timestamp algorithms that is \mbox{$1.68$-competitive}. the family of time\-stamp algorithms also includes a new deterministic 2-competitive on-line algorithm that is different from the move-to-front rule.
dynamic tcp acknowledgement: penalizing long delays. we study the problem of acknowledging a sequence of data packets that are sent across a tcp connection. previous work on the problem has focused mostly on the objective function that minimizes the sum of the number of acknowledgments sent and on the delays incurred for all of the packets. dooly, goldman, and scott presented a deterministic $2$-competitive online algorithm and showed that this is the best competitiveness of a deterministic strategy. recently karlin, kenyon, and randall developed a randomized online algorithm that achieves an optimal competitive ratio of $e/(e-1) \approx 1.58$.in this paper we investigate a new objective function that minimizes the sum of the number of acknowledgments sent and the maximum delay incurred for any of the packets. this function is especially interesting if a tcp connection is used for interactive data transfer between network nodes. the tcp acknowledgment problem with this new objective function is different in structure than the problem with the function considered previously. we develop a deterministic online algorithm that achieves a competitive ratio of $\pi^2/6 \approx 1.644$ and prove that no deterministic algorithm can have a smaller competitiveness. we also study a generalized objective function where delays are taken to the $p$th power for some positive integer $p$. again we give tight upper and lower bounds on the best possible competitive ratio of deterministic online algorithms. the competitiveness is 1 plus an alternating sum of riemann's zeta function and tends to 1.5 as $p\rightarrow \infty$. finally, we consider randomized online algorithms and show that, for our first objective function, no randomized strategy can achieve a competitive ratio smaller than $3/(3 - 2/e)\approx 1.324$. for the generalized objective function we show a lower bound of $2/(2-1/e) \approx 1.225$.
dynamic string searching. optimal bounds are presented for dynamic string searching. if the longest common prefix between a query key x and a currently stored string y is &ell; words, then finding the stored string lexicographically nearest to x takes optimal &thgr;(&radic;log n/log log n + &ell;) time. similarly, we can insert and delete strings from the stored set within this time bound. the space requirements is linear and the time bounds are worst-case.
on nash equilibria for a network creation game. we study a network creation game recently proposed by fabrikant, luthra, maneva, papadimitriou and shenker. in this game, each player (vertex) can create links (edges) to other players at a cost of &alpha; per edge. the goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players.fabrikant et al. conjectured that there exists a constant a such that, for any &alpha; > a, all non-transient nash equilibria graphs are trees. they showed that if a nash equilibrium is a tree, the price of anarchy is constant. in this paper we disprove the tree conjecture. more precisely, we show that for any positive integer n0, there exists a graph built by n &ge; n0 players which contains cycles and forms a non-transient nash equilibrium, for any &alpha; with 1 < &alpha; &le; &radic;n/2. our construction makes use of some interesting results on finite affine planes. on the other hand we show that, for &alpha; &ge; 12n[log n], every nash equilibrium forms a tree.without relying on the tree conjecture, fabrikant et al. proved an upper bound on the price of anarchy of o(&radic;&alpha;), where &alpha; &isin; [2, n2]. we improve this bound. specifically, we derive a constant upper bound for &alpha; &isin; o(&radic;n) and for &alpha; &ge; 12n[log n]. for the intermediate values we derive an improved bound of o(1 + (min{&alpha;2/n, n2/&alpha;})1/3).additionally, we develop characterizations of nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing.
improved parallel integer sorting without concurrent writing. we show that n integers in the range 1..n can be stably sorted on an erew pram using o((log n)1/2) time, o(n(log n)1/2(log log n)1/2) operations and o(n) space. in addition, we are able to stably sort n integers in the range 1..n on a deterministic crew pram in o((log n)3/2) time with o(n(log n)1/2) operations and o(n) space and to stably sort n arbitrary integers on a randomized crew pram within the same complexity bounds with high probability. in each case our algorithm is closer to optimality than all previous algorithms for the stated problem in the stated model, and our third result matches the operation count of the best known sequential algorithm. we also show that m integers in the range 1..m can be sorted in o((log n)2) time with o(n) operations on an erew pram using a nonstandard word length of o(log n log log n log m) bits, thereby greatly improving the upper bound on the word length necessary to sort integers with a linear time-processor product, even sequentially. our algorithms were inspired by, and in one case directly use, the fusion trees recently introduced by fredman and willard.
efficient algorithms for substring near neighbor problem. in this paper we consider the problem of finding the approximate nearest neighbor when the data set points are the substrings of a given text t. specifically, for a string t of length n, we present a data structure which does the following: given a pattern p, if there is a substring of t within the distance r from p, it reports a (possibly different) substring of t within distance cr from p. the length of the pattern p, denoted by m, is not known in advance. for the case where the distances are measured using the hamming distance, we present a data structure which uses &otilde;(n1+1/c) space1 and with &otilde;(n1/c + mno(1)) query time. this essentially matches the earlier bounds of [ind98], which assumed that the pattern length m is fixed in advance. in addition, our data structure can be constructed in time &otilde;(n1+1/c + n1+o(1)m1/3), where m is an upper bound for m. this essentially matches the preprocessing bound of [ind98] as long as the term &otilde;(n1+1/c) dominates the running time, which is the case when, e.g., c < 3.we also extend our results to the case where the distances are measured according to the l1 distance. the query time and the space bound are essentially the same, while the preprocessing time becomes &otilde;(n1+1/c + n1+o(1)m2/3).
instability of fifo in session-oriented networks. we show that the first-in-first-out (fifo) scheduling discipline can be unstable in the (σ,ρ) regulated session model for packet-switched networks. in this model packets are injected into the network in fixed sessions. the total size of the session-i packets injected during the time interval [x, y) is at most σi + ρi(y - x) for some burst parameter σi and rate ρi. the sum of the rates of sessions passing through a server is at most the server speed.previous work on fifo stability either allowed for dynamically changing session paths or else assumed that session-i packets are injected at a constant rate. our result shows that fifo can be unstable for static paths as long as the injections into a session can be temporarily suspended.