waashk/dblp huggingface dataset:
superiority and complexity of the spaced seeds. optimal spaced seeds were introduced by the theoretical computer science community to bioinformatics to effectively increase homology search sensitivity. they are now serving thousands of homology search queries daily. while dozens of papers have been published on optimal spaced seeds since their invention, many fundamental questions still remain unanswered. in this paper, we settle several open questions in this area. specifically, we prove that when the length of a non-uniformly spaced seed is bounded by an exponential function of the seed weight, the seed outperforms strictly the traditional consecutive seed in both (i) the average number of non-overlapping hits and (ii) the asymptotic hit probability. then, we study the computation of the hit probability of a spaced seed, solving three more open questions: (iii) hit probability computation in a uniform homologous region is np-hard and (iv) it admits a ptas; (v) the asymptotic hit probability is computable in exponential time in seed length, independent of the homologous region length.
an optimal online algorithm for packet scheduling with agreeable deadlines. an important issue in ip-based qos networks is the effective management of packets at the router level. specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. in recent work, kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size b. each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. at each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. if b = &infin;, this is the online version of the scheduling problem 1| pj = 1, rj, dj |&sigma; wj uj. (we assume that rj and dj are integers.)
randomized online algorithms for minimum metric bipartite matching. we present the first poly-logarithmic competitive online algorithm for minimum metric bipartite matching. via induction and a careful use of potential functions, we show that a simple randomized greedy algorithm is competitive on a hierarchically separated tree. application of recent results on randomized embedding of metrics into trees yield the poly-logarithmic result for general metrics.
on the number of eularian orientations of a graph. we give efficient randomized schemes to sample and approximately count eulerian orientations of any eulerian graph. eulerian orientations are natural flow-like structures, and welsh has pointed out that computing their number (i)corresponds to evaluating the tutte polynomial at the point (0, &ndash;2) [8,19] and (ii) is equivalent to evaluating &ldquo;ice-type partition functions&rdquo; in statistical physics [20]. our algorithms are based on a reduction to sampling and approximately counting perfect matchings for a class of graphs for which the methods of broder [3, 10] and others [4, 6] apply. a crucial step of the reduction is the &ldquo;monotonicity lemma&rdquo; (lemma 3.3) which is of independent combinatorial interest. roughly speaking, the monotonicity lemma establishes the intuitive fact that &ldquo;increasing the number of constraints applied on a flow problem can only decrease the number of solutions&rdquo;. in turn, the proof of the lemma involves a new decomposition technique which decouples problematically overlapping structures (a recurrent obstacle in handling large combinatorial populations) and allows detailed enumeration arguments. as a byproduct, (i) we exhibit a class of graphs for which perfect and near-perfect matchings are polynomially related, and hence the permanent can be approximated, for reasons other than &ldquo;short augmenting paths&rdquo; (previously the only known approach); and (ii) we obtain a further direct sampling scheme for eulerian orientations which is faster than the one suggested by the reduction to perfect matchings. finally, with respect to our approximate counting algorithm, we give the complementary hardness result, namely, that counting exactly eulerian orientations is #p-complete, and provide some connections with eulerian tours.
on parallel complexity of integer linear programming, gcd and the iterated mod function. we study parallel computational methods for integer linear programming problem with two variables. applying several novel techniques, we prove that this problem is nc-equivalent to computing the continued fraction expansion of a rational number, that is, to computing all the intermediate remainders in the euclidean algorithm applied to two integers, plus to computing the output of an iterated modulo function, with the remainder sequence from the euclidean algorithm (that is, with the continued fraction expansion of a rational number) as its input arguments. the best previously known results are special cases of our theorem.
a time efficient delaunay refinement algorithm. in this paper we present a delaunay refinement algorithm for generating good aspect ratio and optimal size triangulations. this is the first algorithm known to have sub-quadratic running time. the algorithm is based on the extremely popular delaunay refinement algorithm of ruppert. we know of no prior refinement algorithm with an analyzed subquadratic time bound. for many natural classes of meshing problems, our time bounds are comparable to know bounds for quadtree methods.
a general approach for incremental approximation and hierarchical clustering. we present a general framework and algorithmic approach for incremental approximation algorithms. the framework handles cardinality constrained minimization problems, such as the k-median and k-mst problems. given some notion of ordering on solutions of different cardinalities k, we give solutions for all values of k such that the solutions respect the ordering and such that for any k, our solution is close in value to the value of an optimal solution of cardinality k. for instance, for the k-median problem, the notion of ordering is set inclusion and our incremental algorithm produces solutions such that any k and k', k < k', our solution of size k is a subset of our solution of size k'. we show that our framework applies to this incremental version of the k-median problem (introduced by mettu and plaxton [30]), and incremental versions of the k-mst problem, k-vertex cover problem, k-set cover problem, as well as the uncapacitated facility location problem (which is not cardinality-constrained). for these problems we either get new incremental algorithms, or improvements over what was previously known. we also show that the framework applies to hierarchical clustering problems. in particular, we give an improved algorithm for a hierarchical version of the k-median problem introduced by plaxton [31].
fast implementation of depth contours using topological sweep. the concept of location depth was introduced in statistics as a way to extend the univariate notion of ranking to a bivariate configuration of data points. it has been used successfully for robust estimation, hypothesis testing, and graphical display. these require the computation of depth regions, which form a collection of nested polygons. the center of the deepest region is called the tukey median. the only available implemented algorithms for the depth contours and the tukey median are slow, which limits their usefulness. in this paper we describe an optimal algorithm which computes all depth contours in &ogr;(n2) time and space, using topological sweep of the dual arrangement of lines. once the contours are known, the location depth of any point is computed in &ogr;(log2 n) time. we provide fast implementations of these algorithms to allow their use in everyday statistical practice.
efficient construction of unit circular-arc models. in a recent paper, dur&aacute;n, gravano, mcconnell, spinrad and tucker described an algorithm of complexity o(n2) for recognizing whether a graph g with n vertices is a unit circular-arc (uca) graph. furthermore the following open questions were posed in the above paper: (i) is it possible to construct a uca model for g in polynomial time? (ii) is it possible to construct a model, whose extremes of the arcs correspond to integers of polynomial size? (iii) if (ii) is true, could such a model be constructed in polynomial time? in the present paper, we describe a characterization of uca graphs which leads to linear time algorithms for recognizing uca graphs and constructing uca models. furthermore, we construct models whose extreme of the arcs correspond to integers of size o(n). the proposed algorithms provide positive answers to the three above questions.
density graphs and separators. we propose a class of graphs that would occur naturally in finite-element problems, and we prove a bound on separators for this class of graphs. for three-dimensional graphs, our separator bound is $o(n^{2/3})$. we also propose a simple randomized algorithm to find this separator in $o(n)$ time. such an algorithm would be used as a preprocessing step for the domain decomposition method of efficiently solving a finite-element problem on a parallel computer. this paper generalizes ``local graphs'''' of vavasis [1990] to the case of graphs with varying densities of nodes. it also generalizes aspects of miller and thurston''s [1990] ``stable graphs.''''
lower bounds on the size of selection and rank indexes. the rank index problem is the following: preprocess and store a bit string x &isin; {0,1}n on a random access machine with word size w so that rank queries "what is &sigma;ji=1 xi?" for arbitrary values of j can afterwards be easily answered. the selection index problem is the following: preprocess and store a bit string x &isin; {0,1}n so that selection queries "what is the index of the j'th 1-bit in x?" for arbitrary values of j can afterwards be easily answered. the data structure representing x should be an index structure, i.e., the n-bit string x is kept verbatim in [n/w] words and the preprocessing phase adds an r-bit index &phi;(x) with additional information contained in [r/w] words. we are interested in tradeoffs between r, the size of the index measured in bits (the redundancy of the scheme), and t, the worst case time for answering a query.
deterministic identity testing for multivariate polynomials. in this paper we present a simple deterministic algorithm for testing whether a multivariate polynomial f(x1, ..., xn) is identically zero, in time polynomial in m, n, log(d + 1) and h. here m is the number of monomials in f, d is the maximum degree of a variable in f and 2h is the least upper bound on the magnitude of the largest coefficient in f. we assume that f has integer coefficients.the main feature of our algorithm is its conceptual simplicity. the proof uses linnik's theorem which is a deep fact about distribution of primes in an arithmetic progression.
computing sequential equilibria for two-player games. koller, megiddo and von stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear programming and avoiding conversion to normal form. koller and pfeffer pointed out that the strategies obtained by the algorithm are not necessarily sequentially rational and that this deficiency is often problematic for the practical applications. we show how to remove this deficiency by modifying the linear programs constructed by koller, megiddo and von stengel so that pairs of strategies forming a sequential equilibrium are computed. in particular, we show that a sequential equilibrium for a two-player zero-sum game with imperfect information but perfect recall can be found in polynomial time. in addition, the equilibrium we find is normal-form perfect. our technique generalizes to general-sum games, yielding an algorithm for such games which is likely to be prove practical, even though it is not polynomial-time.
fptas for mixed-integer polynomial optimization with a fixed number of variables. we show the existence of an fptas for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.
sublinear time approximate clustering. clustering is of central importance in a number of disciplines including machine learning, statistics, and data mining. this paper has two foci: (1) it describes how existing algorithms for clustering can benefit from simple sampling techniques arising from work in statistics [pol84]. (2) it motivates and introduces a new model of clustering that is in the spirit of the &ldquo;pac (probably approximately correct)&rdquo; learning model, and gives examples of efficient pac-clustering algorithms.
separation and approximation of polyhedral objects. given a family of disjoint polygons p1, p2,&hellip;, pk in the plane, and an integer parameter m, it is np-complete to decide if the pi's can be separated by a polygonal family consisting of m edges, that is, if there exist polygons r1, r2,&hellip;, rk with pairwise-disjoint boundaries such that pi *** ri and &sgr;|ri| &le; m. in three dimensions, the problem of separating even two nested convex polyhedra by a k-facet polyhedron is np-complete. many other extensions and generalizations of the polyhedral separation problem, either to families of polyhedra or to higher dimensions, are also intractable. in this paper, we present efficient approximation algorithms for constructing separating families of near-optimal size. our main results are as follows. in two dimensions, we give an o(n log n) time algorithm for constructing a separating family whose size is within a constant factor of an optimal separating family; n is the number of edges in the input family of polygons. in three dimensions, we can separate a convex polyhedron from a nonconvex polyhedron with a convex polyhedral surface whose facet-complexity is o(log n, times the optimal, where n = |p|+|q| is the complexity of the input polyhedra. our algorithm runs in o(n4) time, but improves to o (n3) time if the two polyhedra are nested and convex. our algorithm for separating a convex polyhedron from a nonconvex polyhedron extends to higher dimensions. in d dimensions, for d &ge; 4, the facet-complexity of the approximation polyhedron is o(d log n) times the optimal, and the algorithm runs in o(nd+1)time. finally, we also obtain results on separating sets of points, a family of convex polyhedra, and separation by non-polyhedral surfaces, such as spherical patches.
a polynomial algorithm to find an independent set of maximum weight in a fork-free graph. the class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. the first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by edmonds in 1965 and then extended to the entire class of claw-free graphs by minty in 1980. recently, alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. in the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.
an optimal bloom filter replacement. this paper considers space-efficient data structures for storing an approximation s' to a set s such that s &sube; s' and any element not in s belongs to s' with probability at most &isin;. the bloom filter data structure, solving this problem, has found widespread use. our main result is a new ram data structure that improves bloom filters in several ways:&bull; the time for looking up an element in s' is o(1), independent of &isin;.&bull; the space usage is within a lower order term of the lower bound.&bull; the data structure uses explicit hash function families.&bull; the data structure supports insertions and deletions on s in amortized expected constant time.the main technical ingredient is a succinct representation of dynamic multisets. we also consider three recent generalizations of bloom filters.
linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. this extended abstract summarizes a new result for the graph compression problem, addressing how to compress a graph g into a binary string z with the requirement that z can be decoded to recover g. graph compression finds important applications in 3d model compression of computer graphics [12, 17-20] and compact routing table of computer networks [7]. for brevity, let a &brvbar;&eth;-graph stand for a graph with property &brvbar;&eth;. the information-theoretically optimal number of bits required to represent an n-node &brvbar;&eth;-graph is &lceil;log2 n&brvbar;&eth;(n)&rceil;, where n&brvbar;&eth;(n) is the number of distinct n-node &brvbar;&eth;-graphs. although determining or approximating the close forms of n&brvbar;&eth;(n) for nontrivial classes of &brvbar;&eth; is challenging, we provide a linear-time methodology for graph compression schemes that are information-theoretically optimal with respect to continuous super-additive functions (abbreviated as optimal for the rest of the extended abstract). specifically, if &brvbar;&eth; satisfies certain properties, then we can compress any n-node m-edge &brvbar;&eth;-graph g into a binary string z such that g and z can be computed from each other in o(m + n) time, and that the bit count of z is at most &brvbar;&acirc;(n) + o(&brvbar;&acirc;(n)) for any continuous super-additive function &brvbar;&acirc;(n) with log2n&brvbar;&eth;(n) &iexcl;&uuml; &brvbar;&acirc;(n) + o(&brvbar;&acirc;(n)). our methodology is applicable to general classes of graphs; this extended abstract focuses on graphs with sublinear genus. for example, if the input n-node &brvbar;&eth;-graph g is equipped with an embedding on its genus surface, which is a reasonable assumption for graphs arising from 3d model compression, then our methodology is applicable to any &brvbar;&eth; satisfying the following statements: f1. the genus of any n-node &brvbar;&eth;-graph is o(n/log2 n); f2. any subgraph of a &brvbar;&eth;-graph remains a &brvbar;&eth;-graph; f3. log n &brvbar;&eth;(n) = &brvbar;&cedil;(n); and f4. there is an integer k = o(1) such that it takes o(n) time to determine whether an o(log(k) n)-node graph satisfies property &brvbar;&eth;. for instance, &brvbar;&eth; can be the property of being a directed 3-colorable simple graph with genus no more than ten. the result is a novel application of planarization algorithm for bounded-genus graphs [5] and separator decomposition tree of planar graphs [9]. rooted trees were the only known nontrivial class of graphs with linear-time optimal coding schemes. he, kao, and lu [11] provided o(n log n)-time compression schemes for planar and plane graphs that are optimal. our results significantly enlarge the classes of graphs that admit efficient optimal compression schemes. more results on various versions of graph compression problems or succinct graph representations can be found in [1-4, 6, 8, 10, 14, 15] and the references therein.
mixing time and long paths in graphs. we prove that regular graphs with large degree and small mixing time contain long paths and some other families of graphs as subgraphs. we present then an efficient algorithm for finding long paths. we apply the results to size ramsey numbers and self-avoiding walks in graphs.
multicoloring unit disk graphs on triangular lattice points. given a pair of non-negative integers m and n, p(m, n) denotes a subset of 2-dimensional triangular lattice points defined by p(m, n) [equation], {(xe1 +ye2 | x &isin; {0, 1,..., m -1}, y &isin; {0, 1,..., n -1}} where e1 [equation] (1,0), e2 [equation] (1/2, &radic;3/2). let tm,n(d) be an undirected graph defined on vertex set p(m, n) satisfying that two vertices are adjacent if and only if the euclidean distance between the pair is less than or equal to d. this paper discusses a necessary and sufficient condition that tm,n(d) is perfect; we show that [&forall;m &isin; z+ tm,n(d) is perfect ] if and only if d &ge; &radic;n2 -3n + 3.given a non-negative vertex weight vector w &isin; zp(m,n)+ a multicoloring of (tm,n(d), &omega;) is an assignment of colors to p(m, n) such that each vertex v &isin; p(m, n) admits w(v) colors and every adjacent pair of two vertices does not share a common color. we also give an efficient algorithm for multicoloring (tm, n (d), w) when p(m, n) is perfect.in general case, our results on the perfectness of p(m, n) implies a polynomial time approximation algorithm for multicoloring (tm, n (d), w). our algorithm finds a multicoloring which uses at most &alpha;(d&omega; + o(d3) colors, where &omega; denotes the weighted clique number. when d = 1, &radic;3, 2, &radic;7, 3, the approximation ratio &alpha;(d) = (4/3), (5/3), (7/4), (5/3), (7/4), respectively. when d > 1, we showed that &alpha;(d) &le; (1 + 2/&radic;3 +2&radic;3-3/d) < 1 + 2/&radic;3 < 2.155.
morphing orthogonal planar graph drawings. we give an algorithm to morph between two planar orthogonal drawings of a graph, preserving planarity and orthogonality. the morph uses a polynomial number of discrete steps. each step is either a linear morph that moves a set of vertices horizontally or vertically; or a "twist" that introduces new bends in the edges incident with one vertex. our morph can be implemented so that inter-vertex distances are well-behaved. this is the first algorithm to provide planarity-preserving morphs with well-behaved complexity for a significant class of graph drawings.
the pure literal rule threshold and cores in random hypergraphs. we describe a technique for determining the thresholds for the appearance of cores in random structures. we use it to determine (i) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r-sat, r &ge; 3, and (ii) the threshold for the appearance of a k-core in a random r-uniform hypergraph for all r, k &ge; 2, r + k > 4.
improved bounds on the average length of longest common subsequences. it has long been known &lsqb;chv&aacute;tal and sankoff 1975&rsqb; that the average length of the longest common subsequence of two random strings of length n over an alphabet of size k is asymptotic to &gamma;kn for some constant &gamma;k depending on k. the value of these constants remains unknown, and a number of papers have proved upper and lower bounds on them. we discuss techniques, involving numerical calculations with recurrences on many variables, for determining lower and upper bounds on these constants. to our knowledge, the previous best-known lower and upper bounds for &gamma;2 were those of dan&ccaron;&iacute;k and paterson, approximately 0.773911 and 0.837623 &lsqb;dan&ccaron;&iacute;k 1994; dan&ccaron;&iacute;k and paterson 1995&rsqb;. we improve these to 0.788071 and 0.826280. this upper bound is less than the &gamma;2 given by steele's old conjecture (see steele &lsqb;1997, page 3&rsqb;) that &gamma;2 &equals; 2/(1 + &sqrt;2)&approx; 0.828427. (as steele points out, experimental evidence had already suggested that this conjectured value was too high.) finally, we show that the upper bound technique described here could be used to produce, for any k, a sequence of upper bounds converging to &gamma;k, though the computation time grows very quickly as better bounds are guaranteed.