waashk/dblp huggingface dataset:
(log log )-competitive dynamic binary search trees. the dynamic optimality conjecture [st85] states that splay trees are competitive (within a constant competitive factor) among the class of all binary search tree (bst) algorithms. despite 20 years of research this conjecture is still unresolved. recently, demaine et al. [dhip04] suggested searching for alternative algorithms which have small but non-constant competitive factors. they proposed tango, a bst algorithm which is nearly dynamically optimal - its competitive ratio is o(log log n) instead of a constant. unfortunately, for many access patterns, such as random and sequential, tango is worse than other bst algorithms by a factor of log log n.in this paper, we introduce the multi-splay tree (mst) data structure, which is the first o(log log n)-competitive bst to simultaneously achieve o(log n) amortized cost and o(log2 n) worst-case cost per query. we also prove the sequential access lemma for msts, which states that sequentially accessing all keys takes linear time. thus, msts are o(log log n)-competitive like tango but, unlike tango, require only o(log n) amortized time per access in an arbitrary sequence and only o(1) amortized time per access during a sequential access sequence.furthermore, we generalize the standard framework for competitive analysis of bst algorithms to include updates (insertions and deletions) in addition to queries. in doing so, we extend the lower bound of wilber [wil89] and demaine et al. [dhip04] to handle these update operations. we show how msts can be modified to support these update operations and be o(log log n)-competitive in the new framework while maintaining the rest of the properties above.
absolute convergence: true trees from short sequences. fast-converging methods for reconstructing phylogenetic trees require that the sequences characterizing the taxa be of only polynomial length, a major asset in practice, since real-life sequences are of bounded length. however, of the half-dozen such methods proposed over the last few years, only two fulfill this condition without requiring knowledge of typically unknown parameters, such as the evolutionary rate(s) used in the model; this additional requirement severely limits the applicability of the methods. we say that methods that need such knowledge demonstrate relative fast convergence, since they rely upon an oracle. we focus on the class of methods that do not require such knowledge and thus demonstrate absolute fast convergence. we give a very general construction scheme that not only turns any relative fast-converging method into an absolute fast-converging one, but also turns any statistically consistent method that converges from sequence of length &ogr;(e&ogr;(diam(t))) into an absolute fast-converging method.
a new property and a faster algorithm for baseball elimination. in the baseball elimination problem, there is a league consisting of n teams. at some point during the season, team i has wi wins and gij games left to play against team j. a team is eliminated if it cannot possibly finish the season in first place or tied for first place. the goal is to determine exactly which teams are eliminated. the problem is not as easy as many sports writers would have you believe, in part because the answer depends not only on the number of games won and left to play but also on the schedule of remaining games. in the 1960's, schwartz showed how to determine whether one particular team is eliminated using a maximum flow computation.this paper indicates that the problem is not as difficult as many mathematicians would have you believe. for each team i, let gi denote the number of games remaining. we prove that there exists a value w* such that team i is eliminated if and only if wi + gi w*. using this surprising fact, we can determine all eliminated teams in time proportional to a single maximum flow computation in a graph with n nodes; this improves upon the previous best known complexity bound by a factor of n.
algorithms for quantified boolean formulas. we present algorithms for solving quantified boolean formulas (qbf, or sometimes qsat) with worst case runtime asymptotically less than o(2n) when the clause-to-variable ratio is smaller or larger than some constant. we solve qbfs in conjunctive normal form (cnf) in o(1.709m) time and space, where m is the number of clauses. extending the technique to a quantified version of constraint satisfaction problems (qcsp), we solve qcsp with domain size d = 3 in o(1.953m) time, and qcsps with d &ge; 4 in o(dm/2+&epsilon;) time and space for &epsilon; < 0, where m is the number of constraints. for 3-cnf qbf, we describe an polynomial space algorithm with time complexity o(1.619n) when the number of 3-cnf clauses is equal to n; the bound approaches 2n as the clause-to-variable ratio approaches 2. for 3-cnf &pi;2-sat (3-cnf qbfs of the form &forall;u1&hellip;uj&exist;xj+1&hellip;xnf), an improved polyspace algorithm has runtime varying from o(1.840m) to o(1.415m), as a particular clause-to-variable ratio increases from 1.
how random is the human genome? now that the human genome is (mostly) sequenced, what do we really know about the statistical properties of that random-looking string of 3 billion a's, c's, g's and t's? the speaker and a group of scientists at rockefeller university (andy dewan, chad hayes, josephine hoh, jurg ott, tony parrado, and richard sackler) have used a little algorithmic theory and some programming to try to get answers.
wavelength assignment and generalized interval graph coloring. in this paper we study wavelength assignment on an optical linesystem without wavelength conversion. consider a set of undirected demands along the line. each demand is carried on a wavelength and any two overlapping demands on the same fiber require distinct wavelengths. suppose &mu; wavelengths are available in the system and each fiber can carry all &mu; wavelengths. we define &ell;(e), the load on link e, to be the smallest integer such that &ell;(e)&mu; is at least the number of demands passing through e. hence, &ell;(e) is the minimum number of fibers required on e in order to support all demands.we present a polynomial-time wavelength assignment algorithm that guarantees each wavelength appears at most &ell;(e) times on each link e. (this generalizes the well-known fact that interval graphs are perfect.) in the presence of moadms (mesh optical add/drop multiplexers), devices that multiplex distinct wavelengths from different fibers into a new fiber, we only need to deploy &ell;(e) fibers per link. on the other hand, if each demand has to stay on a single fiber, as is the case without moadms, we show that some links may require more than &ell;(e) fibers. in fact, we show that it is np-complete to decide if a set of demands can be carried on a given set of fibers, or if there exists a set of fibers with a given total length that can carry all the demands.
assigning chain-like tasks to a chain-like network. we investigate the allocation of a chain-like task system consisting of n tasks to a chain-like network of m computers so as to minimize the bottleneck processing cost. we present an &ogr;(mn) time solution algorithm for this problem. this improves on a sequence of five slower algorithms by bokhari [1988], sheu & chiang [1990], hsu [1993], and young & chan [1993,1994].
asymmetric balanced allocation with simple hash functions. we show that for the asymmetric sequential allocation scheme of v&ouml;cking (2003) one can use very simple hash functions. the hash functions we use are a straightforward extension of the hash functions introduced by dietzfelbinger and woelfel (2003). in order to evaluate a hash function a few arithmetic operations and table lookups suffice. moreover, we show that the scheme has essentially the same behavior if the same balls are allowed to be inserted multiple times (i.e. they may be deleted and reinserted afterwards).
optimal space lower bounds for all frequency moments. we prove that any one-pass streaming algorithm which (ε, &delta;)-approximates the kth frequency moment fk, for any real k &ne; 1 and any ε = &omega;(1/&radic;m), must use &omega;(1/ε&sup2;) bits of space, where m is the size of the universe. this is optimal in terms of ε, resolves the open questions of bar-yossef et al in [3, 4], and extends the &omega;(1/ε&sup2;) lower bound for f0 in [11] to much smaller ε by applying novel techniques. along the way we lower bound the one-way communication complexity of approximating the hamming distance and the number of bipartite graphs with minimum/maximum degree constraints.
a polynomial time approximation scheme for minimum routing cost spanning trees. given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the tree. finding a spanning tree of minimum routing cost is np-hard, even when the costs obey the triangle inequality. we show that the general case is in fact reducible to the metric case and present a polynomial-time approximation scheme valid for both versions of the problem. in particular, we show how to build a spanning tree of an n-vertex weighted graph with routing cost at most $(1+\epsilon)$ of the minimum in time $o(n^{o({\frac{1}{\epsilon}}% )})$. besides the obvious connection to network design, trees with small routing cost also find application in the construction of good multiple sequence alignments in computational biology. the communication cost spanning tree problem is a generalization of the minimum routing cost tree problem where the routing costs of different pairs are weighted by different requirement amounts. we observe that a randomized o(log n log log n)-approximation for this problem follows directly from a recent result of bartal, where n is the number of nodes in a metric graph. this also yields the same approximation for the generalized sum-of-pairs alignment problem in computational biology.
on the approximation of maximum satisfiability. we present a 3/4 polynomial time approximation algorithm for the maximum satisfiability problem: given a set of clauses, find a truth assignment that satisfies the maximum number of clauses. the algorithm applies to the weighted case as well, and involves nontrival application of network flow techniques.
algorithms for subset testing and finding maximal sets. in this paper we consider two related problems: subset testing and finding maximal sets. first, consider a sequence of n operations, where each operation either creates a set, inserts (deletes) an element into (from) a set, queries whether a particular element is in a set, queries whether or not one set is a subset of another, or queries whether or not the intersection of two sets is empty. we show that for any integer k, one can implement subset and intersection testing in time o(n1-(1/k) log n) and all of the other operations in time o(n1/k log n)). it requires o(nk+1)/k) space. when k = 2, this yields a worst case time complexity of o(n1/2 log n) per operation, and uses o(n3/2) space. second, consider a set of sets, where the total size of the input is o(n). we show that one can find those sets that are maximal (a set is maximal if it is not contained in any other set) in time o(mn), where m is the number of maximal sets.
on-line file caching. consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost, maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. specifically, when a requested file is not in the cache, bring it into the cache, pay the retrieval cost, and choose files to remove from the cache so that the total size of files in the cache is at most k. this problem generalizes previous paging and caching problems by allowing objects of arbitrary size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. we give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. on any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h >= k. for any algorithm satisfying the latter bound, we show it is also the case that for most choices of k, the retrieval cost is either insignificant or the competitive ratio is constant. this helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.
detecting short directed cycles using rectangular matrix multiplication and dynamic programming. we present several new algorithms for detecting short fixed length cycles in digraphs. the new algorithms utilize fast rectangular matrix multiplication algorithms together with a dynamic programming approach similar to the one used in the solution of the classical chain matrix product problem. the new algorithms are instantiations of a generic algorithm that we present for finding a directed ck, i.e., a directed cycle of length k, in a digraph, for any fixed k &ge; 3. this algorithm partitions the prospective ck's in the input digraph g = (v,e) into o(logk v) classes, according to the degrees of their vertices. for each cycle class we determine, in o(eck log v) time, whether g contains a ck from that class, where ck = ck(&omega;) is a constant that depends only on !, the exponent of square matrix multiplication. the search for cycles from a given class is guided by the solution of a small dynamic programming problem. the total running time of the obtained deterministic algorithm is therefore o(eck logk+1 v).for c3, we get c3 = 2&omega;/(&omega; + 1) < 1.41 where &omega; < 2.376 is the exponent of square matrix multiplication. this coincides with an existing algorithm of [ayz97].for c4 we get c4 = (4&omega; - 1)/(2&omega; + 1) < 1.48. we can dispense, in this case, of the polylogarithmic factor and get an o(e(4&omega;-1)/(2&omega;+1)) = o(e1.48) time algorithm. this improves upon an o(e3/2) time algorithm of [ayz97].for c5 we get c5 = 3&omega;/(&omega; + 2) < 1.63. the obtained running time of o(e3&omega;/(&omega;+2) log6 v) = o(e1.63) improves upon an o(e5/3) time algorithm of [ayz97].determining ck for k &ge; 6 is a difficult task. we conjecture that ck = (k + 1)&omega;/(2&omega; + k - 1), for every odd k. the values of ck for even k &ge; 6 seem to exhibit a much more complicated dependence on &omega;.
family trees: an ordered dictionary with optimal congestion, locality, degree, and search time. we consider the problem of storing an ordered dictionary data structure over a distributed set of nodes. in contrast to traditional sequential data structures, distributed data structures should ideally have low congestion. we present a novel randomized data structure, called a family tree, to solve this problem. a family tree has optimal expected congestion, uses only a constant amount of state per node, and supports searches and node insertion/deletion in expected o(log n) time on a system with n nodes. furthermore, a family tree supports keys from any ordered domain. because the keys are not hashed, searches have good locality in the sense that intermediate nodes on the search path have keys that are not far outside of the range between the source and destination.
practical approximation algorithms for zero- and bounded-skew trees. the skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. zero- or bounded-skew trees are needed for achieving synchronization in many applications, including network multicasting [21] and vlsi clock routing [3, 18]. in these applications edge weights represent propagation delays, and a signal generated at the root should be received by multiple recipients located at the leaves (almost) simultaneously. the objective is to find zero- or bounded-skew trees of minimum total weight, since the weight of the tree is directly proportional to the amount of resources that must be allocated to the tree. charikar et al. [9] have recently proposed the first strongly polynomial algorithms with proven constant approximation factors, 2e &ap; 5.44 and 16.86, for finding minimum weight zero- and bounded-skew trees, respectively. in this paper we introduce a new approach to these problems, based on zero-skew &ldquo;stretching&rdquo; of spanning trees, and obtain algorithms with improved approximation factors of 4 and 14. for the case when tree nodes are points in the plane and edge weights are given by the rectilinear metric our algorithms find zero- and bounded-skew trees of length at most 3 and 9 times the optimum. this case is of special interest in vlsi clock routing. an important feature of our algorithms is their practical running time, which is asymptotically the same as the time needed for computing the minimum spanning tree.
approximating the two-level facility location problem via a quasi-greedy approach. we propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-lflp). our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. it also relates the minimization 2-lflp problem, in an interesting way, to the maximization version of the single level facility location problem. another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting.this new approach enables us to approximate the metric 2-lflp in polynomial time with a ratio of 1:77, a significant improvement on the previously known approximation ratios. moreover, our approach results in a local improvement procedure for the 2-lflp, which is useful in improving the approximation guarantees for several other multi-level facility location problems.
optimal bounds for matching routing on trees. the permutation routing problem is studied for trees under the matching model. by introducing a novel and useful (so-called) caterpillar tree partition, we prove that any permutation on an n-node tree (and thus graph) can be routed in $\frac{3}{2}n + o(\log n)$ steps. this answers an open problem of alon, chung, and graham [ siam j. discrete math., 7 (1994), pp. 516--530].
shape sensitive geometric permutations. we prove that a set of n unit balls in rd admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry. the constant bound significantly improves upon the &thgr;(nd-1) bound for the balls of arbitrary radii. intrigued by this large gap between the two bounds, we also investigate how the number of geometric permutations varies as a function of shape, size, and spacing of objects. our results include a tight bound of 2d-1 on the geometric permutations of n disjoint rectangular boxes in rd, and a constant bound on the geometric permutations for disks in the plane when the ratio between the largest to smallest disks is bounded. an important consequence of the former theorem is that if the smallest bounding boxes containing a set of geometric objects in rd are pairwise disjoint, then those objects admit only 2d-1 permutations, which is a significant improvement on the &ogr;(n2d-2) bound known for general convex objects.
on directed steiner trees. the directed steiner tree problem is the following: given a directed graph g = (v, e) with weights on the edges, a set of terminals s &sube; v, and a root vertex r, find a minimum weight out-branching t rooted at r, such that all vertices in s are included in t. this problem is known to be np-hard. recently, non-trivial polynomial time approximation algorithms have been developed for this problem with worst case approximation guarantees of o(k&epsilon;) for any fixed &epsilon; > 0. we consider a natural lp relaxation of this problem. using a dual formulation we construct a simple deterministic (d + 1)-approximation algorithm for a special case when the subgraph induced by v \ s is a tree with depth d (for example, this can be shown to include the group steiner tree problem as a special case, by the loss of poly-log factors in the approximation guarantee). we also show that this lp has an integrality gap of &theta;(&radic;k) for the general problem.
jenga. jenga is a popular block game played by two players. each player in her turn has to remove a block from a stack, without toppling the stack, and then add it the top of the stack. we analyze the game mathematically and describe the optimal strategies of both players. we show that 'physics', that seems to play a dominant role in this game, does not really add much to the complexity of the (idealized) game, and that jenga is, in fact, a nim-like game. in particular, we show that a game that starts with n full layers of blocks is a win for the first player if and only if n = 2, or n &equiv; 1, 2 (mod 3) and n &ge; 4. we also suggest some several natural extensions of the game.
computer assisted proof of optimal approximability results. we obtain computer assisted proofs of several spherical volume inequalities that appear in the analysis of semidefinite programming based approximation algorithms for boolean constraint satisfaction problems. these inequalities imply, in particular, that the performance ratio achieved by the max 3-sat approximation algorithm of karloff and zwick is indeed 7/8, as conjectured by them, and that the performance ratio of the max 3-csp algorithm of the author is indeed 1/2. other results are also implied. the computer assisted proofs are obtained using a system called realsearch, written by the author. this system uses interval arithmetic to produce rigorous proofs that certain collections of constraints in real variables have no real solution.
matroids, secretary problems, and online mechanisms. we study a generalization of the classical secretary problem which we call the "matroid secretary problem". in this problem, the elements of a matroid are presented to an online algorithm in random order. when an element arrives, the algorithm observes its value and must make an irrevocable decision regarding whether or not to accept it. the accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. this paper presents an o(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. we leave as an open question the existence of constant-competitive algorithms for general matroids. our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.