waashk/dblp huggingface dataset:
controlled perturbation for delaunay triangulations. most geometric algorithms are idealistic in the sense that they are designed for the real-ram model of computation and for inputs in general position. real inputs may be degenerate and floating point arithmetic is only an approximation of real arithmetic. perturbation replaces an input by a nearby input which is (hopefully) in general position and on which the algorithm can be run with floating point arithmetic. controlled perturbation as proposed by halperin et al. calls for more: control over the amount of perturbation needed for a given precision of the floating point system. or conversely, a control over the precision needed for a given amount of perturbation. halperin et al. gave controlled perturbation schemes for arrangements of polyhedral surfaces, spheres, and circles.we extend their work and point out that controlled perturbation is a general scheme for converting idealistic algorithms into algorithms which can be executed with floating point arithmetic. we also show how to use controlled perturbation in the context of randomized geometric algorithms without deteriorating the running time. finally, we give concrete schemes for planar delaunay triangulations and convex hulls and delaunay triangulations in arbitrary dimensions. we analyze the relation between the perturbation amount and the precision of the floating point system. we also report about experiments with a planar delaunay diagram algorithm.
reconstructing a collection of curves with corners and endpoints. we present an algorithm which provably reconstructs a collection of curves with corners and endpoints from a sample set that satisfies a certain sampling condition. the algorithm outputs a polygonal reconstruction that contains the edges in the correct reconstruction of the curves and such that any additional edge between sample points is justified. furthermore, we show that for any such collection of curves, there exists a sample set such that a slightly modified version of our algorithm outputs exactly the correct reconstruction. the algorithm also performs quite well in practice.
smooth-surface reconstruction in near-linear time. a surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that contains the sample points. recently, several algorithms with a correctness guarantee have been proposed. they have unfortunately a worst-case running time that is quadratic in the size of the input because they are based on the construction of 3-d voronoi diagrams or delaunay tetrahedrizations which can have quadratic size. in this paper, we describe a new algorithm that also has a correctness guarantee but whose worst-case running time is o(n log n) where n is the input size. this is actually optimal. as in some of the previous algorithms, the piece-wise linear approximation produced by the new algorithm is a triangulation which is a subset of the 3-d delaunay tetrahedrization.
approximating the minimum degree spanning tree to within one from the optimal degree. we consider the problem of constructing a spanning tree for a graph g = (v,e) with n vertices whose maximal degree is the smallest among all spanning trees of g. this problem is easily shown to be np-hard. we describe an iterative polynomial time approximation algorithm for this problem. this algorithm computes a spanning tree whose maximal degree is at most o(&dgr; + log n), where &dgr; is the degree of some optimal tree. the result is generalized to the case where only some vertices need to be connected (steiner case) and to the case of directed graphs. it is then shown that our algorithm can be refined to produce a spanning tree of degree at most &dgr; + 1. unless p = np, this is the best bound achievable in polynomial time.
dissections and trees, with applications to optimal mesh encoding and to random sampling. we present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees. this correspondence has interesting consequences for enumeration, mesh compression and random graph sampling.it yields a succinct representation for the set p(n) of n-edge 3-connected planar graphs matching the entropy bound 1/n log |p(n)| = 2+o(1) bits per edge. this solves a theoretical problem in mesh compression, as these graphs abstract the combinatorial part of meshes with spherical topology.once the entropy bound is matched, the guaranteed compression rate can only be improved on subclasses: we achieve the optimal parametric rate 1/n log |p(n, i, j)| bits per edge for graphs of p(n) with i vertices and j faces. this effectively reduces the entropy as soon as |i -j| &gt; n1/2, and achieves the optimal rate for triangulations.it also yields an efficient uniform random sampler for labeled 3-connected planar graphs. using it, the amortized complexity of sampling labeled planar graphs is reduced from the best previously known o(n6.5) to o(n3).
an ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. this paper gives a 3/2 approximation algorithm for the smallest 3-edge connected spanning subgraph of an undirected multigraph. the previous best algorithm of khuller and raghavachari [j. algorithms, 21 (1996), pp. 434--450] has approximation ratio $5/3$. the algorithm of cheriyan and thurimella [siam j. comput., 30 (2000), pp. 528--560] achieves ratio 3/2 for simple graphs. our approach, based on the close relationship between an ear decomposition of a 2-edge connected graph and 3-edge connected components, enables us to achieve running time $o( m \alpha(m,n) )$.
better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. khuller and raghavachari [12] present an approximation algorithm (the kr algorithm) for finding the smallest k-edge connected spanning subgraph (k-ecss) of an undirected multigraph. they prove the kr algorithm has approximation ratio < 1.85. we prove the kr algorithm has approximation ratio &le; 1 + &radic;1/e < 1.61; for odd k this requires a minor modification of the algorithm. this is the bestknown performance bound for the smallest k-ecss problem for arbitrary k. our analysis also gives the best-known performance bound for any fixed value of k &le; 3, e.g., for even k the approximation ratio is &le; 1 + (1 -- 1/k)k/2. our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. we also present a polynomial time implementation of the kr algorithm on multigraphs, running in the time for o(nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies). this complements the implementation of [12] which uses time o((kn)2) and is efficient for small k.
special edges, and approximating the smallest directed -edge connected spanning subgraph. we give two approximation algorithms for finding the smallest k-edge connected spanning subgraph of a digraph. for multidigraphs we achieve performance ratio 2 - 1/3k. this is the first known ratio strictly less than 2. for simple digraphs the best known approximation algorithm is due to cheriyan and thurimella. we improve their analysis of the number of "special edges" of a simple digraph. this improves the performance ratio of their algorithm for simple digraphs from 1 + 4/&radic;k to slightly more than 1 + &radic;2/k, for k &ge; 15. our analysis of the number of special edges is tight for k &ge; 15. for 5 < k < 15 our improved approximation ratio is 1 + 5/k.
upper degree-constrained partial orientations. we wish to orient as many edges as possible in an undirected graph (or multigraph), subject to upper bounds on the indegree and out-degree of each vertex. frank and gy&aacute;rf&aacute;s [2] solve this problem in polynomial time when there are no in-degree bounds, and when every edge can be oriented within the given bounds. however we show that in general the problem is maxsnp-hard. when viewed as a 3-dimensional matching problem the local improvement algorithm of hurkens and schrijver [4] achieves approximation ratio 2/3 -- &epsilon;; we believe is the best previous bound for our problem. we give an lp-rounding algorithm that achieves approximation ratio 3/4.
approximating the smallest -edge connected spanning subgraph by lp-rounding. the smallest k-ecss problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. we examine a natural approximation algorithm based on rounding an lp solution. a tight bound on the approximation ratio is 1 + 3-k for undirected graphs with k > 1 odd, 1 + 2-k for undirected graphs with k even, and 1 + 2-k for directed graphs with k arbitrary. using iterated rounding improves the first upper bound to 1 + 2-k. on the hardness side we show that for some absolute constant c > 0, for any integer k &ge; 2 (k &ge; 1), a polynomial-time algorithm approximating the smallest k-ecss on undirected (directed) multigraphs to within ratio 1 + c-k would imply p = np. &copy; 2008 wiley periodicals, inc. networks, 2009
how to make a square grid framework with cables rigid. this paper solves the problem of making a bipartite digraph strongly connected by adding the smallest number of new edges that preserve bipartiteness. a result of baglivo and graver shows that this corresponds to making a two-dimensional square grid framework with cables rigid by adding the smallest number of new cables. we prove a min-max formula for the smallest number of new edges in the digraph problem and give a corresponding linear-time algorithm. we generalize these results to the problem of making an arbitrary digraph strongly connected by adding the smallest number of new edges, each of which joins vertices in distinct blocks of a given partition of the vertex set.
finding a long directed cycle. consider a digraph with n vertices. for any fixed value k, we present linear- and almost-linear-time algorithms to find a cycle of length &ge; k, if one exists. we also find a cycle that has length &ge; log n/log log n in polynomial time, if one exists. under an appropriate complexity assumption it is known to be impossible to improve this guarantee by more than a log log n factor. our approach is based on depth-first search.
slow mixing of glauber dynamics for the hard-core model on the hypercube. for &lambda; > 0, let &pi;&lambda; be the probability measure on the independent sets of the hypercube {0,1}d in which i is chosen with probability proportional to &lambda;|i|. we study the glauber dynamics, or single-site-update markov chain, whose stationary distribution is &pi;&lambda;, and show that for values of &lambda; tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. the proof combines a conductance argument with combinatorial enumeration methods.
linear phase transition in random linear constraint satisfaction problems. our model is a generalized linear programming relaxation of a much studied random k-sat problem. specifically, a set of linear constraints c on k variables is fixed. from a pool of n variables, k variables are chosen uniformly at random and a constraint is chosen from c also uniformly at random. this procedure is repeated m times independently. we are interested in whether the resulting linear programming problem is feasible. we prove that the feasibility property experiences a linear phase transition, when n &larr; &infin; and m = cn for a constant c. namely, there exists a critical value c* such that, when c < c*, the problem is feasible or is asymptotically almost feasible, as n &larr; &infin;, but, when c > c*, the "distance" to feasibility is at least a positive constant independent of n. our result is obtained using the combination of a powerful local weak convergence method developed in aldous [ald92], [ald01], aldous and steele [as03], steele [ste02] and martingale techniques. by exploiting a linear programming duality, our theorem implies some results for maximum weight matchings in sparse random graphs g(n, &lfloor;cn&rfloor;) on n nodes with cn edges, where edges are equipped with randomly generated weights.
the expected value of random minimal length spanning tree of a complete graph. we consider the number c(n, m) of connected labeled graphs on n nodes and m edges and the intimately related object, the expected length of the minimal spanning tree of a complete graphs with random edge lengths. we use a very simple recursive procedure for computing the values of c(n, m) for computing the expected length of the minimal spanning tree exactly, under the uniform and the exponential distributions. our computations are recursive, scale very well with the size of the problem, and we provide the values of the expected minimal length spanning trees for complete graphs kn with sizes n &le; 45, extending recent results of steele [ste02], and fill and steele [fs04]. the main proof technique is based on introducing an artificial root to a graph and subsequently using a very simple inductive argument.
expansion of product replacement graphs. we establish a connection between the expansion coefficient of the product replacement graph &#x0393;k(g) and the minimal expansion coefficient of a cayley graph of g with k generators. in particular, we show that the product replacement graphs &#x0393;k(psl(2,p)) form an expander family, under assumption that all cayley graphs of psl(2,p), with at most k generators are expanders. this gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].
on contract-and-refine transformations between phylogenetic trees. the inference of evolutionary trees using approaches which attempt to solve the maximum parsimony (mp) and maximum likelihood (ml) optimization problems is a standard part of much of biological data analysis. however, both problems are hard to solve: mp provably np-hard, and ml even harder in practice. consequently, hill-climbing heuristics are used to analyze datasets for phylogeny reconstruction. two primary topological transformations have been used in the most popular heuristics: tbr (tree-bisection-and-reconnection) and ecr (edge-contractions-and-refinements). while most of the popular heuristics exclusively use tbr moves to explore tree space, some recent methods have used ecr in conjunction with tbr and found significant improvements in the speed and accuracy with which they can analyze datasets. in this paper we analyze ecr moves in detail, and provide results on the diameter of the tree space, the neighborhood intersection with tbr, structural analysis of the ecr operation, and an efficient method for sampling uniformly from the 2-ecr neighborhood of a tree. our results should lead to a better understanding of the impact of ecr moves on the performance of heuristic searches.
optimal routing in chord. we propose optimal routing algorithms for chord [1], a popular topology for routing in peer-to-peer networks. chord is an undirected graph on 2b nodes arranged in a circle, with edges connecting pairs of nodes that are 2k positions apart for any k &ge; 0. the standard chord routing algorithm uses edges in only one direction. our algorithms exploit the bidirectionality of edges for optimality. at the heart of the new protocols lie algorithms for writing a positive integer d as the difference of two non-negative integers d&prime; and d&prime; such that the total number of 1-bits in the binary representation of d&prime; and d&prime; is minimized. given that chord is a variant of the hypercube, the optimal routes possess a surprising combinatorial structure.
fair and efficient router congestion control. congestion is a natural phenomenon in any network queuing system, and is unavoidable if the queuing system is operated near capacity. in this paper we study how to set the rules of a queuing system so that all the users have a self-interest in controlling congestion when it happens.routers in the internet respond to local congestion by dropping packets. but if packets are dropped indiscriminately, the effect can be to encourage senders to actually increase their transmission rates, worsening the congestion and destabilizing the system. alternatively, and only slightly more preferably, the effect can be to arbitrarily let a few insistent senders take over most of the router capacity.we approach this problem from first principles: a router packet-dropping protocol is a mechanism that sets up a game between the senders, who are in turn competing for link capacity. our task is to design this mechanism so that the game equilibrium is desirable: high total rate is achieved and is shared widely among all senders. in addition, equilibrium should be reestablished quickly in response to changes in transmission rates. our solution is based upon auction theory: in principle, although not always in practice, we drop packets of the highest-rate sender, in case of congestion. we will prove the game-theoretic merits of our method. we'll also describe a variant of the method with some further advantages that will be supported by network simulations.
analysis of incomplete data and an intrinsic-dimension helly theorem. the analysis of incomplete data is a long-standing challenge in practical statistics. when, as is typical, data objects are represented by points in rd, incomplete data objects correspond to affine subspaces (lines or &delta;-flats). with this motivation we study the problem of finding the minimum intersection radius r(l) of a set of lines or &delta;-flats l: the least r such that there is a ball of radius r intersecting every flat in l. known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because "distances" between flats do not satisfy the triangle inequality. in this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of helly's theorem. this "intrinsic-dimension" helly theorem states: for any family l of &delta;-dimensional convex sets in a hilbert space, there exist &delta; + 2 sets l' &sube; l such that r(l) &le; 2r(l'). based upon this we present an algorithm that computes a (1 + &epsilon;)-core set l' &sube; l,|l'| = o(&delta;4/&epsilon;2), such that the ball centered at a point c with radius (1 + &epsilon;)r(l') intersects every element of l. the running time of the algorithm is o(n&delta;+1dpoly(1/&epsilon;)). for the case of lines or line segments (&delta; = 1), the (expected) running time of the algorithm can be improved to o(nd poly(1/&epsilon;)). we note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space.
improved approximation for universal facility location. the universal facility location problem (unifl) is a generalized formulation which contains several variants of facility location including capacitated facility location (1-cfl) as its special cases. we present a 6 + &epsilon; approximation for the unifl problem, thus improving the 8 + &isin; approximation given by mahdian and pal. our result bridges the existing gap between the unifl problem and the 1-cfl problem.
linear programming and unique sink orientations. we show that any linear program (lp) in n nonnegative variables and m equality constraints defines in a natural way a unique sink orientation of the n-dimensional cube. from the sink of the cube, we can either read off an optimal solution to the lp, or we obtain certificates for infeasibility or unboundedness.this reduction complements the implicit local neighborhoods induced by the vertex-edge structure of the feasible region with an explicit neighborhood structure that allows random access to all 2n candidate solutions. using the currently best sink-finding algorithm for general unique sink orientations, we obtain the fastest deterministic lp algorithm in the ram model, for the central case n = 2m.
on adaptive deterministic gossiping in ad hoc radio networks. we study deterministic algorithms for gossiping problem in ad hoc radio networks. the gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. the efficiency of a communication algorithm in radio networks is very often expressed in terms of: max-eccentricity d, max-indegree &delta;, and size (number of nodes) n of underlying graph of connections. the max-eccentricity d of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u, v) of nodes in the network. the max-indegree &delta; of a network is the maximum of indegrees of its nodes.we propose a new method that leads to several improvements in deterministic gossiping. it combines communication techniques designed for both known as well as unknown ad hoc radio networks. first we show how to subsume the o(dn)-time bound yield by the round-robin procedure proposing a new &otilde;(&radic;dn)-time gossiping algorithm. our algorithm is more efficient than the known &otilde;(n3/2)-time gossiping algorithms [3, 6], whenever d = o(n&alpha;) and &alpha; < 1. for large values of max-eccentricity d, we give another gossiping algorithm that works in time o(d&delta;3/2 log3 n) which subsumes the o(d&delta2 log3 n) upper bound presented in [4].
polynomial interpolation from multiples. we are given an unknown polynomial f &isin; ℤ[x] by a black box which on input a &isin; ℤ returns a value rq &middot; f(a) for some unknown nonzero rational numbers ra. if we have appropriate upper bounds on the numerator and denominator of ra and the degree of f, then the coefficients of f can be computed in probabilistic polynomial time.
distance labeling in graphs. we consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional information). our main interest is in the minimal length of labels needed in different cases. we obtain upper bounds and (most importantly) lower bounds for several interesting families of graphs. in particular, our main results are the following: for general graphs, the length needed is &thgr;(n). for trees, the length needed is &thgr;(log2 n). for planar graphs, we show an upper bound of &ogr;(&radic;n log n) and a lower bound of &ohgr;(n1/3). for bounded degree graphs, we show a lower bound of &ohgr;(&radic;n). the upper bounds for planar graphs and for trees follow by a more general upper bound for graphs with a r(n)- separator. the two lower bounds, however, are obtained by two different arguments that may be interesting in their own right. we also show some lower bounds on the length of the labels, even if it is only required that distances be approximated to a multiplicative factor s. for example, we show that for general graphs the required length is &ohgr;(n). we also consider the problem of the time complexity of the distance function once the labels are computed. we show that there are graphs with optimal labels of length 3 log n, such that if we use any labels with fewer than n bits per label, computing the distance function requires exponential time. a similar result is obtained for planar and bounded degree graphs.