waashk/dblp huggingface dataset:
approximate distance oracles for unweighted graphs in expected () time. let g &equals; (v, e) be an undirected graph on n vertices, and let &delta;(u, v) denote the distance in g between two vertices u and v. thorup and zwick showed that for any positive integer t, the graph g can be preprocessed to build a data structure that can efficiently report t-approximate distance between any pair of vertices. that is, for any u, v &isin; v, the distance reported is at least &delta;(u, v) and at most t&delta;(u, v). the remarkable feature of this data structure is that, for t&ge;3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t-approximate distance query in constant time. they named the data structure &ldquo;approximate distance oracle&rdquo; because of this feature. furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal.in this article, we show that we can actually construct approximate distance oracles in expected o(n2) time if the graph is unweighted. one of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. a (2, 1) spanner of an undirected unweighted graph g &equals; (v, e) is a subgraph (v, &ecirc;), &ecirc; &sube; e, such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2&delta;(u, v) &plus; 1.
faster fixed parameter tractable algorithms for finding feedback vertex sets. a feedback vertex set (fvs) of a graph is a set of vertices whose removal results in an acyclic graph. we show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3n1 &minus; &epsi; vertices, then there is a cycle of length at most 6/&epsi; (for &epsi; &ge; 1/2, we can even improve this to just 6).using this, we obtain a o((12 log k/log log k &plus; 6)k n&omega; algorithm for testing whether an undirected graph on n vertices has a fvs of size at most k. here n&omega; is the complexity of the best matrix multiplication algorithm. the previous best parameterized algorithm for this problem took o((2k &plus; 1)kn2) time.we also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.
finding 3-shredders efficiently. a shredder in an undirected graph is a set of vertices whose removal results in at least three components. a 3-shredder is a shredder of size three. we present an algorithm that, given a 3-connected graph, finds its 3-shredders in time proportional to the number of vertices and edges, when implemented on a ram (random access machine).
succinct ordinal trees with level-ancestor queries. we consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. we focus on static ordinal trees, that is, arbitrary static rooted trees where the children of each node are ordered. the set of operations is essentially the union of the sets of operations supported by previous succinct representations [jacobson 1989; munro and raman 2001; benoit et al. 1999] to which we add the level-ancestor operation.our representation takes 2n &plus; o(n) bits to represent an n-node tree, which is within o(n) bits of the information-theoretic minimum, and supports all operations in o(1) time on the ram model. these operations also provide a mapping from the n nodes of the tree onto the integers &lcub;1, &hellip;, n&rcub;. in addition to the existing motivations for studying such data structures, we are motivated by the problem of representing xml documents compactly so that xpath queries can be supported efficiently.
bipartite roots of graphs. graph h is a root of graph g if there exists a positive integer k such that x and y are adjacent in g if and only if their distance in h is at most k. motwani and sudan [1994] proved the np-completeness of graph square recognition and conjectured that it is also np-complete to recognize squares of bipartite graphs. the main result of this article is to show that squares of bipartite graphs can be recognized in polynomial time. in fact, we give a polynomial-time algorithm to count the number of different bipartite square roots of a graph, although this number could be exponential in the size of the input graph. by using the ideas developed, we are able to give a new and simpler linear-time algorithm to recognize squares of trees and a new algorithmic proof that tree square roots are unique up to isomorphism. finally, we prove the np-completeness of recognizing cubes of bipartite graphs.
the cyclic multi-peg tower of hanoi. variants of the classical tower of hanoi problem evolved in various directions. allowing more than 3 pegs, and imposing limitations on the possible moves among the pegs, are two of these. here, we deal with the case of h&ge;3 pegs arranged on a circle, where moves are allowed only from a peg to the next peg (in the clockwise direction). unlike the multi-peg problem without restrictions on moves between pegs, the complexity of this variant as a function of the number of disks is exponential. we find explicit lower and upper bounds for its complexity for any h, and show how this complexity can be estimated arbitrarily well for any specific h.
secure multiparty computation of approximations. approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. in particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. in this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call secure approximations.we start by extending standard definitions of secure (exact) computation to the setting of secure approximations. our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. we then study the complexity of specific secure approximation problems. in particular, we obtain a sublinear-communication protocol for securely approximating the hamming distance and a polynomial-time protocol for securely approximating the permanent and related &num;p-hard problems.
when indexing equals compression: experiments with compressing suffix arrays and applications. we report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. our experiments indicate that the resulting text index offers state-of-the-art compression. in particular, we require roughly 20&percnt; of the original text size---without requiring a separate instance of the text. we can additionally use a simple notion to encode and decode block-sorting transforms (such as the burrows--wheeler transform), achieving a compression ratio comparable to that of bzip2. we also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.
minimizing mean flow time for uet tasks. we consider the problem of scheduling a set of n unit-execution-time (uet) tasks, with precedence constraints, on m &ge; 1 parallel and identical processors so as to minimize the mean flow time. for two processors, the coffman--graham algorithm gives a schedule that simultaneously minimizes the mean flow time and the makespan. the problem becomes strongly np-hard for an arbitrary number of processors, although the complexity is not known for each fixed m &ge; 3. for arbitrary precedence constraints, we show that the coffman--graham algorithm gives a schedule with a worst-case bound no more than 2, and we give examples showing that the bound is tight. for intrees, the problem can be solved in polynomial time for each fixed m &ge; 1, although the complexity is not known for an arbitrary number of processors. we show that hu's algorithm (which is optimal for the makespan objective) yields a schedule with a worst-case bound no more than 1.5, and we give examples showing that the ratio can approach 1.308999.
the register function for -ary trees. for the register function for t-ary trees, recently introduced by auber et al., we prove that the average is log4n &plus; o(1), if all such trees with n internal nodes are considered to be equally likely.this result remains true for rooted trees where the set of possible out-degrees is finite. furthermore we obtain exponential tail estimates for the distribution of the register function. thus, the distribution is highly concentrated around the mean value.
quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. we consider a class of multivariate recurrences frequently arising in the worst-case analysis of davis-putnam-style exponential-time backtracking algorithms for np-hard problems. we describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. we develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst-case time bounds.
online topological ordering. it is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in o(min&lcub;m3/2logn, m3/2 &plus; n2logn&rcub;) time, an improvement over the best known result of o(mn). in addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. we show that the algorithm runs in time o(mklog2n) for general k and that it can be implemented to run in o(nlog n) time on trees, which is optimal. the algorithm also detects cycles in the input.
this side up! we consider two- and three-dimensional bin-packing problems where 90&deg; rotations are allowed. we improve all known asymptotic performance bounds for these problems. in particular, we show how to combine ideas from strip packing and two-dimensional bin packing to give a new algorithm for the three-dimensional strip packing problem where boxes can only be rotated sideways. we propose to call this problem &ldquo;this side up&rdquo;. our algorithm has an asymptotic performance bound of 9/4.
dense subgraph problems with output-density conditions. we consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. we give approximation algorithms with improved theoretical approximation ratios assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. moreover, we investigate the case where the input graph is bipartite and design a randomized pseudopolynomial time approximation scheme that can become a randomized ptas, even if the size of the optimal output graph is comparatively small. this is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has o(n) vertices.
experimental analysis of dynamic all pairs shortest path algorithms. we present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. we describe our implementations of the recent dynamic algorithms of king [1999] and of demetrescu and italiano [2006], and compare them to the dynamic algorithm of ramalingam and reps and to static algorithms on random, real-world and hard instances. our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.
an approximation algorithm for scheduling malleable tasks under general precedence constraints. in this article, we study the problem of scheduling malleable tasks with precedence constraints. we are given m identical processors and n tasks. for each task the processing time is a function of the number of processors allotted to it. in addition, the tasks must be processed according to the precedence constraints. the goal is to minimize the makespan (maximum completion time) of the resulting schedule. the best previous approximation algorithm (that works in two phases) in lep&egrave;re et al. [2002b] has a ratio 3 &plus; &sqrt;5&approx; 5.236. we develop an improved approximation algorithm with a ratio at most 100/43 &plus; 100(&sqrt;4349 &minus; 7)/2451 &approx; 4.730598. we also show that our resulting ratio is asymptotically tight.
the minimum generalized vertex cover problem. let g &equals; (v, e) be an undirected graph, with three numbers d0(e) &ge; d1(e) &ge; d2(e) &ge; 0 for each edge e &isin; e. a solution is a subset u &sube; v and di(e) represents the cost contributed to the solution by the edge e if exactly i of its endpoints are in the solution. the cost of including a vertex v in the solution is c(v). a solution has cost that is equal to the sum of the vertex costs and the edge costs. the minimum generalized vertex cover problem is to compute a minimum cost set of vertices. we study the complexity of the problem with the costs d0(e) &equals; 1, d1(e) &equals; &alpha; and d2(e) &equals; 0 &forall;e &isin; e and c(v) &equals; &beta;&forall;v &isin; v, for all possible values of &alpha; and &beta;. we also provide 2-approximation algorithms for the general case.
generic quantum fourier transforms. the quantum fourier transform (qft) is a principal ingredient appearing in many efficient quantum algorithms. we present a generic framework for the construction of efficient quantum circuits for the qft by &ldquo;quantizing&rdquo; the highly successful separation of variables technique for the construction of efficient classical fourier transforms. specifically, we apply bratteli diagrams, gel'fand-tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the qft over a wide variety of finite abelian and non-abelian groups, including all families of groups for which efficient qfts are currently known and many new families as well. moreover, our method provides the first subexponential-size quantum circuits for the qft over the linear groups glk(q), slk(q), and the finite groups of lie type, for any fixed prime power q.
minimizing total completion time on uniform machines with deadline constraints. consider n independent jobs and m uniform machines in parallel. each job has a processing requirement and a deadline. all jobs are available for processing at time t &equals; 0. job j must complete its processing before or at its deadline and preemptions are allowed. a set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. we present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time &sum;cj. in the classical &alpha; &verbar; &beta; &verbar; &gamma; scheduling notation, this problem is referred to as qm &verbar; prmt, &dmacr;j &verbar; &sum;cj. it is well known that a generalization of this problem with regard to its machine environment results in an np-hard problem.
efficient algorithms for bichromatic separability. a closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. we present a near-linear algorithm for deciding whether two sets of n points in &#x211d;3 can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double wedge. the latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.
robust subgraphs for trees and paths. consider a graph problem which is associated with a parameter, for example, that of finding a longest tour spanning k vertices. the following question is natural: is there a small subgraph that contains an optimal or near optimal solution for every possible value of the given parameter? such a subgraph is said to be robust. in this article we consider the problems of finding heavy paths and heavy trees of k edges. in these two cases, we prove surprising bounds on the size of a robust subgraph for a variety of approximation ratios. for both problems, we show that in every complete weighted graph on n vertices there exists a subgraph with approximately &alpha;/1&minus;&alpha;2n edges that contains an &alpha;-approximate solution for every k &equals; 1,&hellip;, n &minus; 1. in the analysis of the tree problem, we also describe a new result regarding balanced decomposition of trees. in addition, we consider variants in which the subgraph itself is restricted to be a path or a tree. for these problems, we describe polynomial time algorithms and corresponding proofs of negative results.
oracles for bounded-length shortest paths in planar graphs. we present a new approach for answering short path queries in planar graphs. for any fixed constant k and a given unweighted planar graph g &equals; (v, e), one can build in o(&verbar;v&verbar;) time a data structure, which allows to check in o(1) time whether two given vertices are at distance at most k in g and if so a shortest path between them is returned. graph g can be undirected as well as directed.our data structure works in fully dynamic environment. it can be updated in o(1) time after removing an edge or a vertex while updating after an edge insertion takes polylogarithmic amortized time. besides deleting elements one can also disable ones for some time. it is motivated by a practical situation where nodes or links of a network may be temporarily out of service.our results can be easily generalized to other wide classes of graphs---for instance we can take any minor-closed family of graphs.
the np-completeness column: the many limits on approximation. this is the 25th 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 computers and intractability: a guide to the theory of np-completeness, w. h. freeman & co., new york, 1979, hereinafter referred to as &ldquo;[g&j].&rdquo; previous columns, the first 23 of which appeared in journal of algorithms, will be referred to by a combination of their sequence number and year of appearance, for example, [col 1, 1981]. full bibliographic details on the previous columns as well as downloadable unofficial versions of them can be found at http://www.reseach.att.com/~dsj/columns/. this edition of the column discusses the wide range of lower bounds on approximation guarantees for np-hard optimization problems both in their functional forms and in the hypotheses on which they depend.
online scheduling of splittable tasks. we consider online scheduling of splittable tasks on parallel machines, where the goal is to minimize the last completion time (the makespan). in our model, each task can be split into a limited number of parts, that can then be scheduled independently and in parallel. we consider both the case where the machines are identical and the case where some subset of the machines have a (fixed) higher speed than the others. we design a class of algorithms that allows us to give tight bounds for a large class of cases where tasks may be split into relatively many parts. for identical machines, we also improve upon the natural greedy algorithm in other classes of cases.
an improved algorithm for cioq switches. the problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. to date, the most general model that has been investigated is the standard cioq (combined input and output queued) switch architecture with internal fabric speedup s &ge; 1. cioq switches, that comprise the backbone of packet routing networks, are n &times; n switches controlled by a switching policy that incorporates two components: admission control and scheduling. an admission control strategy is essential to determine the packets stored in the fifo queues in input and output ports, while the scheduling policy conducts the transfer of packets through the internal fabric, from input ports to output ports. the online problem of maximizing the total weighted throughput of cioq switches was recently investigated by kesselman and ros&eacute;n [2003]. they presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in either the speedup or the number of distinct values, or logarithmic in the value range). we introduce the first constant-competitive algorithm for the general case of the problem, with arbitrary speedup and packet values. specifically, our algorithm is 8-competitive, and is also simple and easy to implement.
improved results for data migration and open shop scheduling. the data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. we consider this problem with the objective of minimizing the sum of completion times of all storage devices. it is modeled by a transfer graph, where vertices represent the storage devices, and the edges indicate the data transfers required between pairs of devices. each vertex has a nonnegative weight, and each edge has a release time and a processing time. a vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. the objective is to minimize the sum of weighted completion times of all vertices. kim (journal of algorithms, 55:42--57, 2005) gave a 9-approximation algorithm for the problem when edges have arbitrary processing times and are released at time zero. we improve kim's result by giving a 5.06-approximation algorithm. we also address the open shop scheduling problem, o&verbar;rj&verbar; &sum;wjcj, and show that it is a special case of the data migration problem. queyranne and sviridenko (journal of scheduling, 5:287-305, 2002) gave a 5.83-approximation algorithm for the nonpreemptive version of the open shop problem. they state as an obvious open question whether there exists an algorithm for open shop scheduling that gives a performance guarantee better than 5.83. our 5.06 algorithm for data migration proves the existence of such an algorithm. crucial to our improved result is a property of the linear programming relaxation for the problem. similar linear programs have been used for various other scheduling problems. our technique may be useful in obtaining improved results for these problems as well.