waashk/dblp huggingface dataset:
space-efficient dynamic orthogonal point location, segment intersection, and range reporting. we describe an asymptotically optimal data-structure for dynamic point location for horizontal segments. for n line-segments, queries take o(log n) time, updates take o(log n) amortized time and the data structure uses o(n) space. this is the first structure for the problem that is optimal in space and time (modulo the possibility of removing amortization). we also describe dynamic data structures for orthogonal range reporting and orthogonal intersection reporting. in both data structures for n points (segments) updates take o(log n) amortized time, queries take o(log n+k log n/log log n) time, and the structures use o(n) space, where k is the size of the output. the model of computation is the unit cost ram.
dynamic optimality for skip lists and b-trees. sleator and tarjan [39] conjectured that splay trees are dynamically optimal binary search trees (bst). in this context, we study the skip list data structure introduced by pugh [35]. we prove that for a class of skip lists that satisfy a weak balancing property, the working-set bound is a lower bound on the time to access any sequence. furthermore, we develop a deterministic self-adjusting skip list whose running time matches the working-set bound, thereby achieving dynamic optimality in this class. finally, we highlight the implications our bounds for skip lists have on multi-way branching search trees such as b-trees, (a-b)-trees, and other variants as well as their binary tree representations. in particular, we show a self-adjusting b-tree that is dynamically optimal both in internal and external memory.
universality of random graphs. we prove that asymptotically (as n &rarr; &infin;) almost all graphs with n vertices and 10d n2--1/2d log 1/d n edges are universal with respect to the family of all graphs with maximum degree bounded by d. moreover, we provide a polynomial time, deterministic embedding algorithm to find a copy of each bounded degree graph in every graph satisfying some pseudo-random properties. we also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.
fast algorithms for finding proper strategies in game trees. we show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. our algorithm solves a finite sequence of linear programs and runs in polynomial time. for the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.
a nearly linear time algorithm for the half integral disjoint paths packing. we consider the following problem, which is called the half integral k disjoint paths packing. input: a graph g, k pair of vertices (s1, t1), (s2, t2),&hellip;, (sk, tk) in g (which are sometimes called terminals). output: paths p1,&hellip;, pk in g such that pi joins si and ti for i = 1,2,&hellip;, k, and in addition, each vertex is on at most two of these paths. we present an o(n log n) time algorithm for this problem for fixed k. this improves a result by kleinberg [21] who gave an o(n3) algorithm for this problem. in fact, we also have algorithms running in o(n(1+&epsilon;)) time for any &epsilon; > 0 for these problems, if k is up to o((log log n)2/5) for general graphs, up to o((log n/(log log n))1/4) for planar graphs, and up to o((log n/g/(log log n/g))1/4) for graphs on the surface, where g is the euler genus. furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case. we also obtain o(n log n) algorithms for several optimization problems related to the bounded unsplittable flow problem when the number of terminal pairs is bounded. these results can all carry over to problems involving edge capacities.
on the bichromatic -set problem. we study a bichromatic version of the well-known k-set problem: given two sets r and b of points of total size n and an integer k, how many subsets of the form (r&cap;h)&cup;(b\ h) can have size exactly k over all halfspaces h? in the dual, the problem is asymptotically equivalent to determining the worst-case combinatorial complexity of the k-level in an arrangement of n halfspaces. disproving an earlier conjecture by linhart (1993), we present the first nontrivial upper bound for all k &lt; n in two dimensions: o(nk1/3 + n5/6--&isin;k2/3+2&isin; + k2) for any fixed &isin; > 0. in three dimensions, we obtain the bound o(nk3/2 +n0.5034k2.4932 + k3). incidentally, this also implies a new upper bound for the original k-set problem in four dimensions: o(n2k3/2+n1.5034k2.4932+nk3), which improves the best previous result for all k &lt; n0.923. extensions to other cases, such as arrangements of disks, are also discussed.
graph algorithms for biological systems analysis. the post-genomic era has witnessed an explosion in the quality, quantity and variety of biological data---sequence, structure, and networks. however, when building computational models on these data, some abstractions recur often. in particular, graph-based computational models are a powerful, flexible and efficient way of modeling many biological systems. graph models are used in systems biology where the goal is to understand relationships among biological entities, and in structural bioinformatics where a graph is used to represent the amino acid (or atom) interaction relationships in a protein or the secondary structure base-pairing relationships in rna. for many of these problems, we can develop algorithms that explore the fact that certain key parameters have complexity dependent on the treewidth of the system, which is typically very small for a variety of biological systems. when treewidth is large, we can still use spectral methods to find biologically sound solutions in an efficient manner.
unconditionally reliable message transmission in directed networks. in the unconditionally reliable message transmission (urmt) problem, two non-faulty players, the sender s and the receiver r are part of a synchronous network modeled as a directed graph. s has a message that he wishes to send to r; the challenge is to design a protocol such that after exchanging messages as per the protocol, the receiver r should correctly obtain s's message with arbitrarily small error probability &delta;, in spite of the influence of a byzantine adversary that may actively corrupt up to t nodes in the network (we denote such a urmt protocol as (t, (1 - &delta;))-reliable). while it is known that (2t + 1) vertex disjoint directed paths from s to r are necessary and sufficient for (t, 1)-reliable urmt (that is with zero error probability), we prove that a strictly weaker condition, which we define and denote as (2t, t)-special-connectivity, together with just (t+1) vertex disjoint directed paths from s to r, is necessary and sufficient for (t, (1' - &delta;))-reliable urmt with arbitrarily small (but non-zero) error probability, &delta;. thus, we demonstrate the power of randomization in the context of reliable message transmission. in fact, for any positive integer k > 0, we show that there always exists a digraph gk such that (k, 1)-reliable urmt is impossible over gk whereas there exists a (2k, (1 - &delta;))-reliable urmt protocol, &delta; > 0 in gk. in a digraph g on which (t, (1 - &delta;))-reliable urmt is possible, an edge is called critical if the deletion of that edge renders (t, (1 - &delta;))-reliable urmt impossible. we give an example of a digraph g on n vertices such that g has &omega;(n2) critical edges. this is quite baffling since no such graph exists for the case of perfect reliable message transmission (or equivalently (t, 1)-reliable urmt) or when the underlying graph is undirected. such is the anomalous behavior of urmt protocols (when "randomness meet directedness") that it makes it extremely hard to design efficient protocols over arbitrary digraphs. however, if urmt is possible between every pair of vertices in the network, then we present efficient protocols for the same.
explicit constructions for compressed sensing of sparse signals. over the recent years, a new approach for obtaining a succinct approximate representation of n-dimensional vectors (or signals) has been discovered. for any signal x, the succinct representation of x is equal to ax, where a is a carefully chosen r x n real matrix, r &lt; n. often, a is chosen at random from some distribution over r x n matrices. the vector ax is often refered to as the measurement vector or a sketch of x. although the dimension of ax is much shorter than of x, it contains plenty of useful information about x.
non-clairvoyant scheduling with precedence constraints. we consider edmonds's model (1999) extended by precedence constraints. in our setting, a scheduler has to schedule non-clairvoyantly jobs consisting in dags of tasks arriving over time, each task going through phases of different degrees of parallelism, unknown to the scheduler. as in the original model without precedence constraints, the scheduler is only informed of the arrival and the completion of each task, at the time of these events, and nothing more. furthermore, it is not aware of the dag structure of each job beforehand neither of the precise characteristics of the phases of the tasks that compose each job. we consider the preemptive strategy equi&cir;equi, that divides the processors evenly among the alive jobs and then divides the processing power alloted to each job evenly among its alive tasks. we show that whatever how complex the precedences are, equi&cir;equi is (2 + &epsilon;)-speed 0(&kappa;/&epsilon;)-competitive for the flowtime metric, where &kappa; is the maximum number of independent tasks in each job. that is to say, the flowtime of the schedule computed by equioequi is at a constant ratio of the optimal flowtime as soon as equi is given slightly more than twice the resources as the optimum it is compared to. interestingly, the extra speed needed to obtain a competitive algorithm, namely (2+&epsilon;), is the same in presence of precedence constraints, as in the original setting without precedences studied by edmonds in 1999. this means that the maximum load that the system can handle without diverging, is the same with or without precedence constraints. furthermore, we propose a simple scheme to analyze a special class of schedulers, namely equi-schedulers, which allows to obtain upper and lower bounds on particular precedences structures, such as independent chains, in-trees, out-trees and serial-parallel dags.
catalan structures and dynamic programming in -minor-free graphs. we give an algorithm that, for a fixed graph h and integer k, decides whether an n-vertex h-minor-free graph g contains a path of length k in 2o(&radic;k). no(1) steps. our approach builds on a combination of demaine-hajiaghayi's bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of h-minor-free graphs. this result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. the proof is based on several structural theorems from the graph minors series of robertson and seymour. with a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. our approach can be viewed as a general framework for obtaining time 2o(&radic;k). no(1) algorithms on h-minor-free graph classes.
shuffling cards, adding numbers, and symmetric functions. problems of riffle shuffling cards don't seem to have much to do with problems of analyzing "carries" when adding two integers base 10. both subjects seem remote from modern algebraic combinatorics, where things like quasi-symmetric functions are all the rage. in this talk, i will review these three subjects and show that they are intimately related. for shuffling, i will review the "seven shuffles" theorem (with david bayer) and extensions to modern casino shelf-shufflers (work with susan holmes and jason fulman). for carries, i will review the work of knuth and holte on the process of carries when m integers are added base 6. for symmetric functions, i will explain how much of combinatorics has been unified---theories of permutation enumeration, portions, and partially ordered sets are included.
matroid intersection, pointer chasing, and young's seminormal representation of . we consider the number of queries needed to solve the matroid intersection problem, a question raised by welsh (1976). given two matroids of rank r on n elements, it is known that o(nr1.5) independence queries suffice. however, no non-trivial lower bounds are known for this problem. we make the first progress on this question. we describe a family of instances of rank r = n/2 based on a pointer chasing problem, and prove that (log2 3) n-o (n) queries are necessary to solve these instances. this gives a constant factor improvement over the trivial lower bound of n for matroids of this rank. our proof uses methods from communication complexity and group representation theory. we analyze the communication matrix by viewing it as an operator in the group algebra of the symmetric group and explicitly computing its spectrum.
geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. we present an algorithm for the 3-center problem in (ℝd, l&infin;), i.e., for finding the smallest side length for 3 cubes that cover a given n-point set in ℝd, that runs in o(n log n) time for any fixed dimension d. this shows that the problem is fixed-parameter tractable when parameterized with d. on the other hand, using tools from parameterized complexity theory, we show that this is unlikely to be the case with the k-center problem in (ℝd, l2), for any k &ge; 2. in particular, we prove that deciding whether a given n-point set in ℝd can be covered by the union of 2 balls of given radius is w[1]-hard with respect to d, and thus not fixed-parameter tractable unless fpt=w[1]. our reduction also shows that even an o(no(d))-time alorithm for the latter does not exist, unless snp &sube; dtime(2o(n)).
(almost) optimal coordination mechanisms for unrelated machine scheduling. we investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. our goal is to design local policies that minimize the inefficiency of resulting equilibria. in particular, we design optimal coordination mechanisms for unrelated machine scheduling, and improve the known approximation ratio from &theta;(m) to &theta;(log m), where m is the number of machines. a local policy for each machine orders the set of jobs assigned to it only based on parameters of those jobs. a strongly local policy only uses the processing time of jobs on the the same machine. we prove that the approximation ratio of any set of strongly local ordering policies in equilibria is at least &omega;(m). in particular, it implies that the approximation ratio of a greedy shortest-first algorithm for machine scheduling is at least &omega;(m). this closes the gap between the known lower and upper bounds for this problem, and answers an open question raised by ibarra and kim [16], and davis and jaffe [10]. we then design a local ordering policy with the approximation ratio of &theta;(log m) in equilibria, and prove that this policy is optimal among all local ordering policies. this policy orders the jobs in the non-decreasing order of their inefficiency, i.e, the ratio between the processing time on that machine over the minimum processing time. finally, we show that best responses of players for the inefficiency-based policy may not converge to a pure nash equilibrium, and present a &theta;(log2 m) policy for which we can prove fast convergence of best responses to pure nash equilibria.
a near-linear time algorithm for computing replacement paths in planar directed graphs. let g = (v(g), e(g)) be a weighted directed graph and let p be a shortest path from s to t in g. in the replacement paths problem we are required to compute for every edge e in p, the length of a shortest path from s to t that avoids e. the fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in p is removed from the graph in its turn and the distance from s to t in the modified graph is computed. the running time of this algorithm is o (mn + n2 log n), where n = |v(g)| and m = |e(g)|. the replacement paths problem is strongly motivated by two different applications. first, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [21, 13] repeatedly computes the replacement paths from s to t. its running time is o(kn(m + n log n)). second, the computation of vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. an open question raised by nisan and ronen [16] asks whether it is possible to compute the vickrey pricing faster than the trivial algorithm described in the previous paragraph. in this paper we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. in particular, the algorithm computes the lengths of the replacement paths in o(n log3 n) time. this result immediately improves the running time of the two applications mentioned above by almost a linear factor. our algorithm is obtained by combining several new ideas with a data structure of klein [12] that supports multi-source shortest paths queries in planar directed graphs in logarithmic time. our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). in that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time &otilde;(h), where h is the number of hops in the replacement path. in addition, we can handle the variant in which vertices should be avoided instead of edges.
on the connectivity of dynamic random geometric graphs. we provide the first analytical results for the connectivity of dynamic random geometric graphs --- a model of mobile wireless networks in which vertices move in random directions, and an edge exists between two vertices if their euclidean distance is below a given value. we provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. we believe the formal tools developed in this work could be of use in more concrete settings, in the same manner as the development of connectivity threshold for static random geometric graphs has affected a lot of research done on ad hoc networks. in the process of proving results for the dynamic case we also obtain new asymptotically precise bounds for the probability of the existence of a component of fixed size l, l &ge; 2, for the static case.
a fractional model of the border gateway protocol (bgp). the border gateway protocol (bgp) is the interdomain routing protocol used to exchange routing information between autonomous systems (ases) in the internet today. while intradomain routing protocols such as rip are basically distributed algorithms for solving shortest path problems, the graph theoretic problem that bgp is trying to solve is called the stable paths problem (spp). unfortunately, unlike shortest path problems, it has been shown that instances of spp can fail to have a solution and so bgp can fail to converge. we define a fractional version of spp and show that all such instances of fractional spp have solutions. we also show that while these solutions exist they are not necessarily half-integral.
l(2, 1)-labelling of graphs. an l(2, 1)-labelling of a graph is a function f from the vertex set to the positive integers such that |f(x) - f(y)| &ge; 2 if dist(x, y) = 1 and |f(x) - f(y)| &ge; 1 if dist(x, y) = 2, where dist(x, y) is the distance between the two vertices x and y in the graph g. the span of an l(2, 1)-labelling f is the difference between the largest and the smallest labels used by f plus 1. in 1992, griggs and yeh conjectured that every graph with maximum degree &delta; &ge; 2 has an l(2, 1)-labelling with span at most &delta;2 + 1. by settling this conjecture for &delta; sufficiently large, we prove the existence of a constant c such that the span of any graph of maximum degree &delta; is at most &delta; 2 + c.
succinct approximate convex pareto curves. we study the succinct approximation of convex pareto curves of multiobjective optimization problems. we propose the concept of &epsilon;-convex pareto (&epsilon;-cp) set as the appropriate one for the convex setting, and observe that it can offer arbitrarily more compact representations than &epsilon;-pareto sets in this context. we characterize when an &epsilon;-cp can be constructed in polynomial time in terms of an efficient routine comb for optimizing (exactly or approximately) monotone linear combinations of the objectives. we investigate the problem of computing minimum size &epsilon;-convex pareto sets, both for discrete (combinatorial) and continuous (convex) problems, and present general algorithms using a comb routine. for bi-objective problems, we show that if we have an exact comb optimization routine, then we can compute the minimum &epsilon;-cp for continuous problems (this applies for example to bi-objective linear programming and markov decision processes), and factor 2 approximation to the minimum &epsilon;-cp for discrete problems (this applies for example to bi-objective versions of polynomial-time solvable combinatorial problems such as shortest paths, spanning tree, etc.). if we have an approximate comb routine, then we can compute factor 3 and 6 approximations respectively to the minimum &epsilon;-cp for continuous and discrete bi-objective problems. we consider also the case of three and more objectives and present some upper and lower bounds.
on the hitting times of quantum versus random walks. the hitting time of a classical random walk (markov chain) is the time required to detect the presence of -- or equivalently, to find -- a marked state. the hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. in this paper we define new monte carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing las vegas type definitions. in particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. further, we prove that for any reversible ergodic markov chain p, the quantum hitting time of the quantum analogue of p has the same order as the square root of the classical hitting time of p. we also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. in doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. for the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk. finally, we present new quantum algorithms for the detection and finding problems. the complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. the detection algorithm is based on phase estimation and is particularly simple. the finding algorithm combines a similar phase estimation based procedure with ideas of tulsi from his recent theorem [19] for the 2d grid. extending his result, we show that for any state-transitive markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.