waashk/dblp huggingface dataset:
perturbations and vertex removal in a 3d delaunay triangulation. though delaunay triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional delaunay triangulation is still a problem in practice.we propose a simple method that allows to remove any vertex even when the points are in very degenerate configurations. the solution is available in cgal.
delaunay triangulations approximate anchor hulls. recent results establish that a subset of the voronoi diagram of a point set that is sampled from the smooth boundary of a shape approximates the medial axis. the corresponding question for the dual delaunay triangulation is not addressed in the literature. we show that, for two-dimensional shapes, the delaunay triangulation approximates a specific structure which we call anchor hulls. as an application we demonstrate that our approximation result is useful for the problem of shape matching.
shape dimension and approximation from samples. there are many scientific and engineering applications where an automatic detection of shape dimension from sample data is necessary. topological dimensions of shapes constitute an important global feature of them. we present a voronoi based dimension detection algorithm that assigns a dimension to a sample point which is the topological dimension of the manifold it belongs to. based on this dimension detection, we also present an algorithm to approximate shapes of arbitrary dimension from their samples. our empirical results with data sets in three dimensions support our theory.
improved embeddings of graph metrics into random trees. over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (v, d) can be approximated to within o(log n) by distributions d over trees on the point set v [3, 10]. however, when the metric (v, d) is the shortest-path metric of an edge weighted graph g = (v, e), a natural requirement is to obtain such a result where the support of the distribution d is only over subtrees of g. for a long time, the best result satisfying this stronger requirement was a exp {&radic;log n log log n} distortion result of alon et al. [1]. in a recent breakthrough, elkin et al. [9] improved the distortion to o(log2 n log log n). (the best lower bound on the distortion is &omega;(log n), say, for the n-vertex grid [1].)in this paper, we give a construction that improves the distortion to o(log2 n), improving slightly on the eest construction. the main contribution of this paper is in the analysis: we use an algorithm which is similar to one used by eest to give a distortion of o(log3 n), but using a new probabilistic analysis, we eliminate one of the logarithmic factors. the ideas and techniques we use to obtain this logarithmic improvement seem orthogonal to those used earlier in such situations---e.g., seymour's decomposition scheme [4, 9] or the cutting procedures of ckr/frt [5, 10], both which do not seem to give a guarantee of better than o(log2 n log log n) for this problem. we hope that our ideas (perhaps in conjunction with some of these others) will ultimately lead to an o(log n) distortion embedding of graph metrics into distributions over their spanning trees.
certifying and repairing solutions to large lps how good are lp-solvers? state-of-the-art linear programming (lp) solvers give solutions without any warranty. solutions are not guaranteed to be optimal or even close to optimal. of course, it is generally believed that the solvers produce optimal or at least close to optimal solutions.we have implemented a system lpex which allows us to check this belief. more precisely, given an lp and a basis b, it determines whether the basis is primal feasible and/or dual feasible. it can also find the optimum starting from an arbitrary basis (or from scratch). it uses exact arithmetic to guarantee correctness of the results. the system is efficient enough to be applied to medium- to large-scale lps. we present results from the netlib benchmark suite.
tree exploration with little memory. a robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. the robot has no a priori knowledge of the topology of the tree or of its size, and its aim is to traverse all the edges. while o(log δ) bits of memory suffice to explore any tree of maximum degree δ if stopping is not required, we show that bounded memory is not sufficient to explore with stop all trees of bounded degree (indeed ω (log log log n) bits of memory are needed for some such trees of size n). for the more demanding task requiring to stop at the starting node after completing exploration, we show a sharper lower bound ω (log n) on required memory size, and present an algorithm to accomplish this task with o(log2 n)-bit memory, for all n-node trees.
an improved approximation algorithm for combinatorial auctions with submodular bidders. we explore the allocation problem in combinatorial auctions with submodular bidders. we provide an e/e-1 approximation algorithm for this problem. moreover, our algorithm applies to the more general class of xos bidders. by presenting a matching unconditional lower bound in the communication model, we prove that the upper bound is tight for the xos class.our algorithm improves upon the previously known 2-approximation algorithm. in fact, we also exhibit another algorithm which obtains an approximation ratio better than 2 for submodular bidders, even in the value queries model.throughout the paper we highlight interesting connections between combinatorial auctions with xos and submodular bidders and various other combinatorial optimization problems. in particular, we discuss coverage problems and online problems.
lattice approximation and linear discrepency of totally unimodular matrices. this paper shows that the lattice approximation problem for totally unimodular matrices a &isin; rm&times;n can be solved efficiently and optimally via a linear programming approach. the complexity of our algorithm is &ogr;(log m) times the complexity of finding an extremal point of a polytope in rn described by 2(m + n) linear constraints. we also consider the worst-case approximability. this quantity is usually called linear discrepancy lindisc(a). for any totally unimodular m &times; n matrix a we show lindisc(a) &le; min{1 - 1/n+1, 1 - 1/m}. this bound is sharp. it proves spencer's conjecture lindisc(a) &le; (1 - 1/n+1) herdisc(a) for totally unimodular matrices. this seems to be the first time that linear programming is successfully used for a discrepancy problem.
non-independent randomized rounding. we investigate an extension of the randomized rounding technique introduced by raghavan and thompson. whereas their approach only requires that each variable is rounded with probabilities given by its fractional part, we also impose this condition on several sums of variables. thus in particular our roundings are not independent.we show that such non-independent randomized roundings exist if and only if the hypergraph corresponding to these dependencies is totally unimodular.
matrix rounding with low error in small submatrices. we show that any real valued matrix a can be rounded to an integer one b such that the error in all 2 x 2 (geometric) submatrices is less than 1.5, that is, we have |aij - bij| < 1 and |&sigma;i+1k=i &sigma;j+1l=j(akl - bkl| < 1.5 for all i, j. more precisely, an error of less than 1.5 - 3-2mn + 3-d+1 can be achieved in time o(mnd).
neighborhood preserving hashing and approximate queries. let $d \subseteq \sigma^n$ be a dictionary. we look for efficient data structures and algorithms to solve the following approximate query problem: given a query $u \in \sigma^n$ list all words $v \in d$ that are close to u in hamming distance.the problem reduces to the following combinatorial problem: hash the vertices of the n-dimensional hypercube into buckets so that (1) the c-neighborhood of each vertex is mapped into at most k buckets and (2) no bucket is too large.lower and upper bounds are given for the tradeoff between k and the size of the largest bucket. these results are used to derive bounds for the approximate query problem.
selecting the median. improving a long-standing result of schönhage, paterson, and pippenger [ j. comput. system sci., 13 (1976), pp. 184--199] we show that the median of a set containing $n$ elements can always be found using at most $c \cdot n$ comparisons, where c<2.95.
balls and bins models with feedback. we examine generalizations of the classical balls and bins models, where the probability a ball lands in a bin is proportional to the number of balls already in the bin raised to some exponent p. such systems exhibit positive or negative feedback, depending on the exponent p, with a phase transition occurring at p = 1. similar models have proven useful in economics and chemistry; for example, systems with positive feedback (p > 1) tend naturally toward monopoly. we provide several results and useful heuristics for these models, including showing a bound on the time to achieve monopoly with high probability.
sampling algorithms for regression and applications. we present and analyze a sampling algorithm for the basic linear-algebraic problem of l2 regression. the l2 regression (or least-squares fit) problem takes as input a matrix a &isin; rn&times;d (where we assume n &gt; d) and a target vector b &isin; rn, and it returns as output z = minx&isin;rd |b - ax|2. also of interest is xopt = a+b, where a+ is the moore-penrose generalized inverse, which is the minimum-length vector achieving the minimum. our algorithm randomly samples r rows from the matrix a and vector b to construct an induced l2 regression problem with many fewer rows, but with the same number of columns. a crucial feature of the algorithm is the nonuniform sampling probabilities. these probabilities depend in a sophisticated manner on the lengths, i.e., the euclidean norms, of the rows of the left singular vectors of a and the manner in which b lies in the complement of the column space of a. under appropriate assumptions, we show relative error approximations for both z and xopt. applications of this sampling methodology are briefly discussed.
fully persistent lists with catenation. this paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. this problem arises in the implementation of list-based and functional programming languages. a solution is proposed requiring constant time and space for each stack operation except catenation, which requires o(log log k) time and space. here k is the number of stack operations done before the catenation. all the resource bounds are amortized over the sequence of operations.
fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most o(log@d) times the optimum, @d being the maximum degree of the input network. this is best-possible if np@?dtime[n^o^(^l^o^g^l^o^g^n^)] and if the processors are required to run in polynomial-time. we then show how to construct dominating sets that have the above properties, as well as the ''low stretch'' property that any two adjacent nodes in the network have their dominators at a distance of at most o(logn) in the output network. (given a dominating set s, a dominator of a vertex u is any v@?s such that the distance between u and v is at most one.) we also show our time bounds to be essentially optimal.
localizing a robot with minimum travel. we consider the problem of localizing a robot in a known environment modeled by a simple polygon p. we assume that the robot has a map of p but is placed at an unknown location inside p. from its initial location, the robot sees a set of points called the visibility polygon v of its location. in general, sensing at a single point will not suffice to uniquely localize the robot, since the set h of points in p with visibility polygon v may have more than one element. hence, the robot must move around and use range sensing and a compass to determine its position (i.e., localize itself). we seek a strategy that minimizes the distance the robot travels to determine its exact location.we show that the problem of localizing a robot with minimum travel is np-hard. we then give a polynomial time approximation scheme that causes the robot to travel a distance of at most (k - 1)d, where k = |h|, which is no greater than the number of reflex vertices of p, and d is the length of a minimum length tour that would allow the robot to verify its true initial location by sensing. we also show that this bound is the best possible.
on validating planar worlds. we present an optimal linear time algorithm for solving a map validation problem: a robot equipped with one portable marker must determine the correctness of a given map of its graph-like world, modelled as a possibly non-planar embedding of a planar graph.
an approximation algorithm for cutting out convex polygons. we provide an o(logn)-approximation algorithm for the following problem. given a convex n-gon p, drawn on a convex piece of paper, cut p out of the piece of paper in the cheapest possible way. no polynomial-time approximation algorithm was known for this problem posed in 1985.
approximation algorithms for tsp with neighborhoods in the plane. in the euclidean tsp with neighborhoods (tspn), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. as a generalization of the classical euclidean tsp, tspn is also np-hard. in this paper, we present new approximation results for the tspn, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a ptas for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. further, we give a linear-time o(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines.
optimal constrained graph exploration. we address the problem of exploring an unknown graph g = (v, e) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. in both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. in the tethered robot case, if the tether (rope) has length l, then the robot must remain within distance l from the start node s. in the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing c edges. the efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. we present an algorithm for a tethered robot which explores the graph in &ogr;(&brvbar;e&brvbar;) edge traversals. the problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a &ogr;(&brvbar;e&brvbar;) algorithm. this improves on the previous best known bound of &ogr;(&brvbar;e&brvbar; + &brvbar;v&brvbar;log 2&brvbar;v&brvbar;) in [4]. since the lower bound for the graph exploration problems is &brvbar;e&brvbar;, our algorithm is optimal, thus answering the open problem of awerbuch, betke, rivest, and singh [3].
broadcast scheduling: when fairness is fine. we investigate server scheduling policies to minimize user perceived latency in a client-server system where the server uses broadcast communication. we show that no o(1)-competitive online algorithms exist for this problem. we consider the intuitive algorithm bequi that broadcasts all requested files at a rate proportional to the number of out-standing requests for that file. we show that bequi is an o(1)-speed o(1)-approximation algorithm. we give another algorithm bequi-edf, and show that bequi-edf is also an o(1)-speed o(1)-approximation algorithm. however, bequi-edf has the advantage that it preempts each broadcast on average at most once and will never preempt if the data items have unit size.
a maiden analysis of longest wait first. we consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. the algorithm longest wait first (lwf) always services the page where the aggregate waiting times of the outstanding requests for that page is maximized. we provide the first non-trivial analysis of the worst case performance of lwf. on the negative side, we show that lwf is not s-speed o(1)-competitive for s < 1+&radic;5/2. on the positive side, we show that lwf is 6-speed o(1)-competitive.
cake cutting really is not a piece of cake. we consider the well-known cake cutting problem in which a protocol wants to divide a cake among n &ge; 2 players in such a way that each player believes that they got a fair share. the standard robertson-webb model allows the protocol to make two types of queries, evaluation and cut, to the players. a deterministic divide-and-conquer protocol with complexity o(n log n) is known. we provide the first an &omega;(n log n) lower bound on the complexity of any deterministic protocol in the standard model. this improves previous lower bounds, in that the protocol is allowed to assign to a player a piece that is a union of intervals and only guarantee approximate fairness. we accomplish this by lower bounding the complexity to find, for a single player, a piece of cake that is both rich in value, and thin in width. we then introduce a version of cake cutting in which the players are able to cut with only finite precision. in this case, we can extend the &omega;(n log n) lower bound to include randomized protocols.
morphing between polylines. given two non-intersecting simple polylines in the plane, we study the problem of continuously transforming or morphing one polyline into the other. our morphing strategies have the desirable property that every intermediate polyline is also simple. we also guarantee that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. our algorithms are based on the morphing width, a new metric we have developed for measuring the similarity between two polylines. we develop an algorithm that computes the morphing width of the two polylines and constructs a corresponding morphing strategy in &ogr;(n2 log2 n) time using &ogr;(n2) space, where n is the total number of vertices in the polylines. we describe another algorithm that computes a factor-2 approximation of the morphing width and a corresponding morphing scheme in &ogr;(n log n) time.
pattern matching for sets of segments. in this paper we present algorithms for a number of problems in geometric pattern matching where the input consist of a collections of segments in the plain. our work consists of two main parts. in the first, we address problems and measures that relate to collections of orthogonal line segments in the plane. such collections arise naturally from problems in mapping buildings and robot exploration. we propose a new measure of segment similarity called a coverage measure, and present efficient algorithms for maximising this measure between sets of axis-parallel segments under translations. our algorithms run in time &ogr;(n3polylogn) in the general case, and run in time &ogr;(n3polylogn) for the case when all segments are horizontal. in addition, we show that when restricted to translations that are only vertical, the hausdorff distance between two sets of horizontal segments can be computed in time roughly &ogr;(n3/2polylog n). these algorithms are significant improvements over the general algorithm of chew et al. that takes time &ogr;(n4 log2 n). in the second part of this paper we address the problem of matching polygonal chains. we study the well known fr&eacute;chet distance, and present the first algorithm for computing the fr&eacute;chet distance under general translations. our methods also yield algorithms for computing a generalization of the fr&eacute;chet distance, and we present a simple approximation algorithm for the fr&eacute;chet distance and its generalization that runs in time &ogr;(n2polylogn).
a combinatorial algorithm for computing a maximum independent set in a t-perfect graph. we present a combinatorial polynomial time algorithm to compute a maximum stable set of a t-perfect graph. the algorithm rests on an &epsilon;-approximation algorithm for general set covering and packing problems and is combinatorial in the sense that it does not use an explicit linear programming algorithm or methods from linear algebra or convex geometry. instead our algorithm is based on basic arithmetic operations and comparisons of rational numbers which are of polynomial binary encoding size in the input.
an improved approximation algorithm for virtual private network design. virtual private network design deals with the reservation of capacities in a network, such that the nodes can share communication. each node in the network has associated upper bounds on the amount of flow that it can send to the network and receive from the network respectively. the problem then is to reserve capacities at minimum cost and to compute paths between every pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths.in this paper we present a simple 4.74-approximation algorithm for virtual private network design. the previous best approximation algorithm for this problem achieves a ratio of 5.55 (gupta, kumar, and roughgarden stoc'03).
0/1 optimization and 0/1 primal separation are equivalent. the 0/1 primal separation problem is: given an extreme point x of a 0/1 polytope p and some point x*, find an inequality which is tight at x, violated by x* and valid for p or assert that no such inequality exists. it is known that this separation variant can be reduced to the standard separation problem for p. we show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. this implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent.we apply this result to the perfect matching problem. here, primal separation is easier than its standard version. we present an algorithm for primal separation, which rests only on simple max-flow computations. consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. in contrast, the known standard separation method involves padberg and rao's minimum odd cut algorithm, which itself is based on the construction of a gomory-hu tree.