waashk/dblp huggingface dataset:
randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting. we present new algorithms for approximate range counting, where, for a specified &epsilon; > 0, we want to count the number of data points in a query range, up to relative error of &epsilon;. we first describe a general framework, adapted from cohen [10], for this task, and then specialize it to two important instances of range counting: halfspaces in r3 and disks in the plane. the technique reduces the approximate range counting problem to that of finding the minimum rank of a data object in the range, with respect to a random permutation of the input.a major technical step in our analysis, which we believe to be of independent interest, is a bound of o(n log n) on the expected complexity of the overlay of all the voronoi faces that are generated during a randomized incremental construction of the voronoi diagram of n points in the plane. the same bound holds for the expected complexity of the overlay of all the faces of the minimization diagram of the lower envelope of n planes in r3, or for the expected complexity of the overlay of all the normal (or gaussian) diagram faces of the convex hull of n points in r3, that are generated during a randomized incremental construction of the lower envelope or of the hull, respectively. all these bounds are tight in the worst case.the first bound leads to an algorithm that, for a query point x &isin; r2, efficiently retrieves the sequence of nearest neighbors of x in p, over the random insertion process. a query takes o(log n) expected time, and the expected storage size is o(n log n). similarly, the other bounds lead to an algorithm that, for a query direction &omega; &isin; s2, efficiently retrieves the sequence of the convex hull vertices that are touched by the planes with outward direction &omega; that support the convex hull during the random insertion process. again, a query takes o(log n) expected time, and the expected storage size is o(n log n). these algorithms are used as the main component in the approximate range counting technique that we present, for ranges that are halfspaces in r3 or disks in the plane.
union-find with deletions. in the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. the operation union(a, b, c) replaces sets a and b in the partition by their union, given the name c. the operation find(x) returns the name of the set containing the element x. in this paper we revisit the union-find problem in a context where the underlying partitioned universe is not fixed. specifically, we allow a delete(x) operation which removes the element x from the set containing it. we consider both worst-case performance and amortized performance. in both settings the challenge is to dynamically keep the size of the structure representing each set proportional to the number of elements in the set which may now decrease as a result of deletions.for any fixed k, we describe a data structure that supports find and delete in o(logkn) worst-case time and union in o(k) worst-case time. this matches the best possible worst-case bounds for find and union in the classical setting. furthermore, using an incremental global rebuilding technique we obtain a reduction converting any union-find data structure to a union-find with deletions data structure. our reduction is such that the time bounds for find and union change only by a constant factor. the time it takes to delete an element x is the same as the time it takes to find the set containing x plus the time it takes to unite a singleton set with this set.in an amortized setting a classical data structure of tarjan supports a sequence of m finds and at most n unions on a universe of n elements in o(n + m&alpha;(m + n, n, log n)) time where &alpha;(m, n, l) = min{k | ak(&lfloor;m/n&rfloor;) > l} and ai(j) is ackermann's function as described in [6]. we refine the analysis of this data structure and show that in fact the cost of each find is proportional to the size of the corresponding set. specifically, we show that one can pay for a sequence of union and find operations by charging a constant to each participating element and o(&alpha;(m, n, log(l))) for a find of an element in a set of size l. we also show how keep these amortized costs for each find and each participating element while allowing deletions. the amortized cost of deleting an element from a set of l elements is the same as the amortized cost of finding the element; namely, o(&alpha;(m, n, log(l))).
faster kinetic heaps and their use in broadcast scheduling. we describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being fixed, is a linear function of time. the kinetic heap is a simple example of a kinetic data structure of the kind considered by basch, guibas, and hershberger. kinetic heaps have many applications in computational geometry, and previous implementations were designed to address these applications. we describe an additional application, to broadcast scheduling. each of our kinetic heap implementations improves on previous implementations by being simpler or asymptotically faster for some or all applications.
faster approximation schemes for fractional multicommodity flow problems. we present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k. we show that by modifying the algorithms by garg and k&ouml;nemann [1998] and fleischer [2000], we can reduce their running time on a graph with n vertices and m edges from &otilde;(&epsiv;&minus;2(m2 &plus; km)) to &otilde;(&epsiv;&minus;2m2) for an implicit representation of the output, or &otilde;(&epsiv;&minus;2(m2 &plus; kn for an explicit representation, where &otilde;(f) denotes a quantity that is o(f logo(1)m). the implicit representation consists of a set of trees rooted at sources (there can be more than one tree per source), and with sinks as their leaves, together with flow values for the flow directed from the source to the sinks in a particular tree. given this implicit representation, the approximate value of the concurrent flow is known, but if we want the explicit flow per commodity per edge, we would have to combine all these trees together, and the cost of doing so may be prohibitive. in case we want to calculate explicitly the solution flow, we modify our schemes so that they run in time polylogarithmic in nk (n is the number of nodes in the network). this is within a polylogarithmic factor of the trivial lower bound of time &omega;(nk) needed to explicitly write down a multicommodity flow of k commodities in a network of n nodes. therefore our schemes are within a polylogarithmic factor of the minimum possible dependencies of the running time on the number of commodities k.
root comparison techniques applied to computing the additively weighted voronoi diagram. this work examines algebraic techniques for comparing quadratic algebraic numbers, thus yielding methods for deciding key predicates in various geometric constructions. our motivation and main application concerns a dynamic algorithm for computing the additively weighted voronoi diagram in the plane. we propose effficient, exact, and complete methods, which are crucial for a fast and robust implementation of these predicates and the overall algorithm. our first contribution is to minimize, on the one hand, the algebraic degree of the computed quantities, thus optimizing precision and, on the other hand, the total number of arithmetic operations. we focus on the hardest predicate, which involves quadratic polynomials, and detail the corresponding algorithms, which are based on polynomial sturm sequences; ancillary tools include geometric invariants, multivariate resultants, and polynomial factorization. our last contribution is a general and efficient implementation, which has been extensively tested in order to demonstrate the practical performance of our methods and the improvements achieved over existing approaches.
static and kinetic geometric spanners with applications. it is well known that the delaunay triangulation is a spanner graph of its vertices. in this paper we show that any bounded aspect ratio triangulation in two and three dimensions is a spanner graph of its vertices as well. we extend the notion of spanner graphs to environments with obstacles and show that both the constrained delaunay triangulation and bounded aspect ratio conforming triangulations are spanners with respect to the corresponding visibility graph. we also show how to kinetize the constrained delaunay triangulation. using such time-varying triangulations we describe how to maintain sets of near neighbors for a set of moving points in both unconstrained and constrained environments. such nearest neighbor maintenance is needed in many virtual environments where nearby agents interact. finally, we show how to use the constrained delaunay triangulation in order to maintain the relative convex hull of a set of points moving inside a simple polygon.
a new constructive root bound for algebraic expressions. computing effective root bounds for constant algebraic expressions is a critical problem in the exact geometric computation approach to robust geometric programs. classical root bounds are often non-constructive. recently, various authors have proposed bounding methods which might be called constructive root bounds. for the important class of radical expressions, burnikel et al (bfms) have provided a constructive root bound which, in the division-free case, is an improvement over previously known bounds and is essentially tight. in the presence of division, their bound requires a quadratic blowup in root bit-bound compared to the division-free case. we present a new constructive root bound that avoids this quadratic blowup and which is applicable to a more general class of algebraic expressions. this leads to dramatically better performance in some computations. we also give an improved version of the degree-measure bound from mignotte and bfms. we describe our implementation in the context of the core library, and report on some experimental results.
learning markov networks: maximum bounded tree-width graphs. markov networks are a common class of graphical models used in machine learning. such models use an undirected graph to capture dependency information among random variables in a joint probability distribution. once one has chosen to use a markov network model, one aims to choose the model that &ldquo;best explains&rdquo; the data that has been observed&mdash;this model can then be used to make predictions about future data. we show that the problem of learning a maximum likelihood markov network given certain observed data can be reduced to the problem of identifying a maximum weight low-treewidth graph under a given input weight function. we give the first constant factor approximation algorithm for this problem. more precisely, for any fixed treewidth objective k, we find a treewidth-k graph with an f(k) fraction of the maximum possible weight of any treewidth-k graph.
two and higher dimensional pattern matching in optimal expected time. algorithms with optimal expected running time are presented for searching the occurrences of a two-dimensional m x m pattern p in a two-dimensional n x n text t over an alphabet of size c. the algorithms are based on placing in the text a static grid of test points, determined only by n, m, and c (not dynamically by earlier test results). using test strings read from the test points the algorithms eliminate as many potential occurrences of p as possible. the remaining potential occurrences are separately checked for actual occurrences. a suitable choice of the test point set leads to algorithms with expected running time o(n2logc m2/m2) using the uniform bernoulli model of randomness. this is shown to be optimal by a generalization of a one-dimensional lower bound result by yao. experimental results show that the algorithms are efficient in practice, too. the method is also generalized for the k mismatches problem. the resulting algorithm has expected running time o(kn2logc m2/m2), provided that $k\leq(m\lfloor m/\lceil\log_c m^2\rceil\rfloor-1)/2$.\ all algorithms need preprocessing of p which takes time and space o(m2). the text processing can be done on-line, using a rather small window. the algorithms easily generalize to d-dimensional matching for any d.
on the convergence time of a path-vector protocol. we study the running time of a particular path-vector protocol for distributively and asynchronously computing shortest paths in a network to a given target node t. we study two cases. in both, the protocol starts with each node possibly knowing some path to t, subject to conditions discussed in the paper. in the first case, the "withdrawal case," all edges incident to the target are cut. we prove that in this case, the protocol always terminates but may need exponential time to do so, if the nodes "fire" (i.e., execute) in an adversarially chosen order, even if the initial paths are shortest. if the graph is a clique, the protocol terminates in polynomial time. if, on the other hand, the nodes fire in random order, and the graph is arbitrary, then the algorithm terminates in polynomial expected time. in the second case, the "announcement case," in which new edges incident to t appear, we prove that the protocol terminates in polynomial time, regardless of the firing order.this protocol is interesting since it models the shortest-path protocol used by bgp, the interdomain routing protocol of the internet, in the absence of policy.
online topological ordering. it is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in o(min{m3/2 log n m3/3 + n2 log n}) time, an improvement over the best known result of o(mn). in addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. we show that the algorithm runs in time o(mk log2 n) for general k and that it can be implemented to run in o(n log n) time on trees, which is optimal. if the input contains cycles, the algorithm detects this.
labeling schemes for flow and connectivity. this paper studies labeling schemes for flow and connectivity functions. a flow labeling scheme using o(logn?log[^(w)])-bit labels is presented for general n-vertex graphs with maximum (integral) capacity [^(w)]. this is shown to be asymptotically optimal. for edge-connectivity, this yields a tight bound of q(log2 n) bits. a k-vertex connectivity labeling scheme is then given for general n-vertex graphs using at most 3logn bits for k = 2, 5logn bits for k = 3 and 2klogn bits for k < 3. finally, a lower bound of w(klogn) is established for k-vertex connectivity on n-vertex graphs where k is polylogarithmic in n.
max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. max-tolerance graphs can be regarded as generalized interval graphs, where two intervals ii and ij only induce an edge in the corresponding graph iff they overlap for an amount of at least max{ti, tj} where ti is an individual tolerance parameter associated to each interval ii. a new geometric characterization of max-tolerance graphs as intersection graphs of isosceles right triangles, shortly called semi-squares, leverages the solution of various graph-theoretic problems in connection with max-tolerance graphs. first, we solve the maximal and maximum cliques problem. it arises naturally in dna sequence analysis where the maximal cliques might be interpreted as functional domains carrying biologically meaningful information. we prove an upper bound of o(n3) for the number of maximal cliques in max-tolerance graphs and give an efficient o(n3) algorithm for their computation. in the same vein, the semi-square representation yields a simple proof for the fact that this bound is asymptotically tight, i.e., a class of max-tolerance graphs is presented where the instances have &omega;(n3) maximal cliques. additionally, we answer an open question posed in [8] by showing that max-tolerance graphs do not contain complements of cycles cn for n > 9. by exploiting the new representation more deeply, we can go even further and prove that the recognition problem for max-tolerance graphs is np-hard.
on finding minimal 2-connected subgraphs. we present efficient parallel algorithms for the problems of finding a minimal 2-edge-connected spanning subgraph of a 2-edge-connected graph and finding a minimal biconnected spanning subgraph of a biconnected graph. the parallel algorithms for both problems run in polylog time using a linear number of pram processors. we also give sequential algorithms for these problems that run in time o(m+n log n) where n and m denote the number of vertices and edges, respectively, in the input graph.
the hidden subgroup problem and permutation group theory. we employ concepts and tools from the theory of finite permutation groups in order to analyse the hidden subgroup problem via quantum fourier sampling (qfs) for the symmetric group. we show that under very general conditions both the weak and the random-strong form (strong form with random choices of basis) of qfs fail to provide any advantage over classical exhaustive search. in particular we give a complete characterisation of polynomial size subgroups, and of primitive subgroups, that can be distinguished from the identity subgroup with the above methods. furthermore, assuming a plausible group theoretic conjecture for which we give supporting evidence, we show that weak and random-strong qfs for the symmetric group have no advantage whatsoever over classical search.
balanced allocation on graphs. it is well known that if n balls are inserted into n bins, with high probability, the bin with maximum load contains (1 + o(1)) log n/log log n balls. azar, broder, karlin, and upfal [1] showed that instead of choosing one bin, if d &ge; 2 bins are chosen at random and the ball in serted into the least loaded of the d bins, the maximum load reduces drastically to log log n/log d + o(1). in this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. we show that for n balls and n bins, if the graph is almost regular with degree n&epsilon;, where &epsilon; is not too small, the previous bounds on the maximum load continue to hold. precisely, the maximum load is log log n + o(1/&epsilon;) + o(1). so even if the graph has degree n&omega;(1/log log n), the maximum load is o(log log n). for general &delta;-regular graphs, we show that the maximum load is log log n + o(log n/log (&delta;/log4 n)) + o(1) and also provide an almost matching lower bound of log log n + log n/log (&delta; log n). further this does not hold for non-regular graphs even if the minimum degree is high.v&ouml;cking [29] showed that the maximum bin size with d choice load balancing can be further improved to o(log log n/d) by breaking ties to the left. this requires d random bin choices. we show that such bounds can be achieved by making only two random accesses and querying d/2 contiguous bins in each access. by grouping a sequence of n bins into 2n/d groups, each of d/2 consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is o(log log n/d) with high probability. furthermore, it also turns out that this partitioning into aligned groups of size d/2 is also essential in achieving this bound, that is, instead of choosing two aligned groups, if we simply choose random but possibly unaligned random sets of d/2 consecutive bins, then the maximum load jumps to &omega;(log log n/log d) even if the two sets are always chosen to be disjoint.
loss-bounded analysis for differentiated services. we consider a network providing differentiated services (diffserv) which allow network service providers to offer different levels of quality of service (qos) to different traffic streams. we focus on loss and first show that only trivial bounds could be obtained by means of traditional competitive analysis. then we introduce a new approach for estimating loss of an online policy called loss-bounded analysis. in loss-bounded analysis the loss of an online policy are bounded by the loss of an optimal offline policy plus a constant fraction of the benefit of an optimal offline policy. we derive tight upper and lower bounds for various settings of diffserv parameters using the new loss-bounded model. we believe that loss-bounded analysis is an important technique that may complement traditional competitive analysis and provide new insight and interesting results.
generating all vertices of a polyhedron is hard. we&#x00a0;show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. more precisely, given a family of negative (directed) cycles, it is an np-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless p=np. as a corollary, we solve in the negative two well-known generating problems from linear programming: (i)&#x00a0;given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. yet, for generating maximal feasible subsystems the complexity remains open. (ii)&#x00a0;given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. yet, in the case of bounded polyhedra the complexity remains open. equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.
on approximating rectangle tiling and packing. our study of tiling and packing with rectangles in two-dimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and motion estimation in video compression by block matching, among others. an example of the problems that we tackle is the following: given an n by n array a of positive numbers, find a tiling using at most p rectangles (that is, no two rectangles must overlap, and each array element must fall within some rectangle) that minimizes the maximum weight of any rectangle; here the "weight" of a rectangle is the sum of the array elements that fall within it. if the array a were one-dimensional, this problem could be easily solved by dynamic programming. we prove that in the two-dimensional case it is np-hard to approximate this problem to within a factor of 1.25. on the other hand, we provide a near-linear time algorithm that returns a solution at most 2.5 times the optimal. other rectangle tiling and packing problems that we study have similar properties: while it is easy to solve them optimally in one dimension, the two-dimensional versions become np-hard. we design efficient approximation algorithms for these problems.
on local search and placement of meters in networks. this work is motivated by the problem of placing pressure-meters in fluid networks. the problem is formally defined in graph-theoretic terms as follows. given a graph, find a cotree (complement of a tree) incident upon the minimum number of vertices. we show that this problem is np-hard and max snp-hard. we design an algorithm with an approximation factor of $2 + \epsilon$ for this problem for any fixed $\epsilon >0$. this approximation bound comes from the analysis of a local search heuristic, a common practical optimization technique that does not often allow formal worst-case analysis. the algorithm is made very efficient by finding restrictive definitions of the local neighborhoods to be searched. we also exhibit a polynomial time approximation scheme for this problem when the input is restricted to planar graphs.