waashk/dblp huggingface dataset:
semi-online maintenance of geometric optima and measures. we give the first nontrivial worst-case results for dynamic versions of various basic geometric optimization and measure problems under the semi-online model, where during the insertion of an object we are told when the object is to be deleted. problems that we can solve with sublinear update time include the hausdorff distance of two point sets, discrete 1-center, largest empty circle, convex hull volume in three dimensions, volume of the union of axis-parallel cubes, and minimum enclosing rectangle. the decision versions of the hausdorff distance and discrete 1-center problems can be solved fully dynamically. some applications are mentioned.
an optimal randomized algorithm for maximum tukey depth. we present the first optimal algorithm to compute the maximum tukey depth (also known as location or halfspace depth) for a non-degenerate point set in the plane. the algorithm is randomized and requires o(n log n) expected time for n data points. in a higher fiexed dimension d &ge; 3, the expected time bound is o(nd-1), which is probably optimal as well. the result is obtained using an interesting variant of the author's randomized optimization technique, capable of solving "implicit" linear-programming-type problems; some other applications of this technique are briefly mentioned.
on levels in arrangements of surfaces in three dimensions. a favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. we propose the first technique that can deal with more general surfaces in three dimensions. for example, in an arrangement of n "pseudo-planes" or "pseudo-spheres" (where each triple of surfaces has at most two common intersections), we prove that there are at most o(n2.9986) vertices of any given level.
finding the shortest bottleneck edge in a parametric minimum spanning tree. the result. parametric optimization problems that concern graphs with continuously changing edge weights have been explored by numerous researchers, with motivation ranging from sensitivity analysis to mobile-data applications. for instance, dey [5] has shown that for an undirected graph with n vertices and m edges where the edge weights are linear functions in one parameter ("time"), the minimum spanning tree (mst) can undergo at most o(mn1/3) changes (edge swaps). agarwal et al. [1] have given data structures to maintain the mst over time, with a cost of o(n2/3 polylog n) per change. fernandez-baca et al. [7] have given an algorithm to compute all changes to the mst in o(mn log n) total time.
all-pairs shortest paths for unweighted undirected graphs in time. we revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. we present new algorithms with the following running times:[equation]these represent the best time bounds known for the problem for all m &lt; n1.376. we also obtain a similar type of result for the diameter problem for unweighted directed graphs.
a dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. we present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take o(log3 n) expected amortized time, deletions take o(log6 n) expected amortized time, and extreme-point queries take o(log2 n) worst-case time. this is the first method that guarantees polylogarithmic update and query cost for arbitrary sequences of insertions and deletions, and improves the previous o(n&epsilon;)-time method by agarwal and matou&scaron;ek a decade ago. as a consequence, we obtain similar results for nearest neighbor queries in two dimensions and improved results for numerous fundamental geometric problems (such as levels in three dimensions and dynamic euclidean minimum spanning trees in the plane).
on hierarchical routing in doubling metrics. we study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with small amount of routing information stored at each vertex). we say that a metric (x, d) has doubling dimension dim(x) at most &alpha; if every set of diameter d can be covered by 2&alpha; sets of diameter d/2. (a doubling metric is one whose doubling dimension dim(x) is a constant.) we show how to perform (1 + &tau;)-stretch routing on metrics for any 0 < t &le; 1 with routing tables of size at most (&alpha;/&tau;)o(&alpha;) log2 &delta; bits with only (&alpha;/&tau;)o(&alpha;) log &delta; entries, where &delta; is the diameter of the graph; hence the number of routing table entries is just &tau;-o(1) log &delta; for doubling metrics. these results extend and improve on those of talwar (2004).we also give better constructions of sparse spanners for doubling metrics than those obtained from the routing tables above; for &tau; > 0, we give algorithms to construct (1 + &tau;)-stretch spanners for a metric (x, d) with maximum degree at most (2 + 1/&tau;)o(dim(x)), matching the results of das et al. for euclidean metrics.
dynamic dictionary matching and compressed suffix trees. recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length n from o(n log n) bits to o(n) bits, while allowing very efficient pattern matching [10, 13]. yet the compressed nature of such indices also makes them difficult to update dynamically. this paper presents the first o(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text t in o(|t | log2 n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. this work can be regarded as a generalization of the compressed representation of static texts. our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an o(d)-bit data structure for a dynamic collection of patterns of total length d that can support the dictionary matching query efficiently. when compared with the o(d log d)-bit suffix tree based solution of amir et al., the compact solution increases the query time by roughly a factor of log d only. in the study of the above results, we also derive the first o(n)-bit representation for maintaining n pairs of balanced parentheses in o(log n/log log n) time per operation, matching the time complexity of the previous o(n log n)-bit solution.
extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling. we study online scheduling of jobs to minimize the flow time and stretch on parallel machines. we consider algorithms that are given extra resources so as to compensate the lack of future information. recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using o(1) times faster machines, the algorithm srpt (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and hdf (highest density first) is o(1)-competitive for weighted flow time [6]. using extra unit-speed machines instead of faster machines is more challenging. this paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. it shows that competitive results via faster machines can be transformed to similar results via extra machines, and hence giving the first algorithms that, using o(1) times unit-speed machines, are 1-competitive for flow time and stretch and o(1)-competitive for weighted flow time, respectively.
non-migratory online deadline scheduling on multiprocessors. in this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. let i be any set of jobs that can be completed by some migratory offline schedule on m processors. we show that i can also be completed by a non-migratory online schedule using m speed-5.828 processors (i.e., processors of 5.828 times faster). this result supplements the previous results that i can also be completed by a non-migratory offline schedule using 6m unit-speed processors [8] or a migratory online schedule using m speed-2 processors [13]. our result is based on a simple conservative scheduling algorithm called park which commits a processor to a job only when the processor has zero commitment before its deadline. a careful analysis of park further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). park also finds application in overloaded systems; it gives the first online non-migratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.
the space complexity of pass-efficient algorithms for clustering. we present multiple pass streaming algorithms for a basic clustering problem for massive data sets. if our algorithm is allotted 2l passes, it will produce an approximation with error at most &epsilon; using &otilde;(k3/&epsilon;2/l) bits of memory, the most critical resource for streaming computation. we demonstrate that this tradeoff between passes and memory allotted is intrinsic to the problem and model of computation by proving lower bounds on the memory requirements of any l pass randomized algorithm that are nearly matched by our upper bounds. to the best of our knowledge, this is the first time nearly matching bounds have been proved for such an exponential tradeoff for randomized computation.in this problem, we are given a set of n points drawn randomly according to a mixture of k uniform distributions and wish to approximate the density function of the mixture. the points are placed in a datastream (possibly in adversarial order), which may only be read sequentially by the algorithm. we argue that this models, among others, the datastream produced by a national census of the incomes of all citizens.
on semidefinite programming relaxations for graph coloring and vertex cover. we investigate the power of a strengthened sdp relaxation for graph coloring whose value is equal to a variant of the lov&aacute;sz &thetasym;-function. we show families of graphs where the value of the relaxation is 2 + &epsilon; for any fixed &epsilon; > 0, yet the chromatic number is n&delta; for some fixed &delta; > 0, which is a function of &epsilon;. this demonstrates the bound provided by the sdp is not strong enough to color a 3-colorable graph with no(1) colors.kleinberg and goemans considered an sdp relaxation for vertex cover whose value is n - &thetasym;1/2 (&thetasym;1/2 being the variant of the &thetasym;-function introduced by schrijver). they asked whether this is within a ratio of 2 - &epsilon; of the optimal vertex cover for any &epsilon; > 0. our construction answers this question negatively.
spreading metrics for vertex ordering problems. we design approximation algorithms for the vertex ordering problems minimum linear arrangement, minimum containing interval graph, and minimum storage-time product, achieving approximation factors of o&radic;log n log log n), o&radic;log n log log n), and o&radic;log t log log t), respectively, the last running in time polynomial in t (t being the sum of execution times). the technical contribution of our paper is to introduce l22 spreading metrics" (that can be computed by semidefinite programming) as relaxations for both undirected and directed "permutation metrics," which are induced by permutations of {1, 2, . . ., n}. the techniques introduced in the recent work of arora, rao and vazirani can be adapted to exploit the geometry of such l22 spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. in addition to their applications to approximation algorithms, the study of such l22 spreading metrics as relaxations of permutation metrics is interesting in its own right. we show how our results imply that, in a certain sense we make precise, l22 spreading metrics approximate permutation metrics on n points to a factor of o&radic;log n log log n).
a tight threshold for metric ramsey phenomena. in this paper, we examine the metric ramsey problem for the normed spaces lp: given some 1 &le; p &le; &infin;, &alpha; &ge; 1 and an integer n, we ask for the largest m such that every n-point metric space contains an m-point subspace which embeds into lp with distortion at most &alpha;. bartal, linial, mendel and naor show in [3] that in the case of 1 &le; p &le; 2, the dependence of m on &alpha; undergoes a phase transition at &alpha; = 2. the case of p > 2 was left as an open problem. we show that the phase transition occurs around &alpha; = 2 for all p &ge; 1. the basis of our result is a proof that there exist {1, 2} metrics which require distortion arbitrarily close to 2 for embedding into lp. in order to show this, we develop new tools for analyzing embeddings of random metrics into lp.
a robust maximum completion time measure for scheduling. one popular measure for evaluating the performance of scheduling algorithms, is the maximum response time of any job (makespan). typically the objective is to find a schedule that minimizes the maximum response time over all jobs. one drawback of this measure is that a relatively small number of jobs in the request set could cause the maximum response time to be very high. thus, this measure reflects local rather than global properties of the request set. in this paper we consider a robust generalization of this measure. our goal is to minimize t, such that a given fraction of jobs can be scheduled with a response time of at most t. we demonstrate the applicability of this measure in the context of broadcast scheduling. we show that in the online setting no constant factor online approximation is possible for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling. we give a factor 5, polynomial time offline approximation algorithm for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling.
minimizing wirelength in zero and bounded skew clock trees. an important problem in vlsi design is distributing a clock signal to synchronous elements in a vlsi circuit so that the signal arrives at all elements simultaneously. the signal is distributed by means of a clock routing tree rooted at a global clock source. the difference in length between the longest and shortest root-leaf path is called the skew of the tree. the problem is to construct a clock tree with zero skew (to achieve synchronicity) and minimal sum of edge lengths (so that circuit area and clock tree capacitance are minimized).we give the first constant-factor approximation algorithms for this problem and its variants that arise in the vlsi context. for the zero skew problem in general metric spaces, we give an approximation algorithm with a performance guarantee of 2e. for the l1 version on the plane, we give an (8/ln 2)-approximation algorithm.
algorithms for facility location problems with outliers. facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. a significant shortcoming of this formulation is that a few very distant clients, called outliers, can exert a disproportionately strong influence over the final solution. in this paper we explore a generalization of various facility location problems (k-center, k-median, uncapacitated facility location etc) to the case when only a specified fraction of the customers are to be served. what makes the problems harder is that we have to also select the subset that should get service. we provide generalizations of various approximation algorithms to deal with this added constraint.
directed metrics and directed graph partitioning problems. the theory of embeddings of finite metrics has provided a powerful toolkit for graph partitioning problems in undirected graphs. the connection comes from the fact that the integrality gaps of mathematical programming relaxations for sparsest cut in undirected graphs is exactly equal to the minimum distortion required to embed certain metrics into l1. no analog of this metric embedding theory exists for directed (asymmetric) metrics, the natural distance functions that arise in considering mathematical relaxations for directed graph partioning problems. we initiate a study of metric embeddings for directed metrics, motivated by understanding directed variants of sparsest cut.it turns out that there are two different ways to formulate sparsest cut in directed graphs (depending on whether one insists on partitioning the graph into two pieces or not). different subclasses of directed metrics arise in the consideration of mathematical relaxations for these two formulations and the embedding questions that result are quite different. unlike in the undirected case, where the natural host space is l1, the host space in the directed case is not obvious and depends on the problem formulation. our work is a first step at understanding this space of directed metrics, the resulting embedding questions and their relationships to directed graph partitioning problems.
the complexity of quantitative concurrent parity games. we consider two-player infinite games played on graphs. the games are concurrent, in that at each state the players choose their moves simultaneously and independently, and stochastic, in that the moves determine a probability distribution for the successor state. the value of a game is the maximal probability with which a player can guarantee the satisfaction of her objective. we show that the values of concurrent games with &omega;-regular objectives expressed as parity conditions can be decided in np &cap; conp. this result substantially improves the best known previous bound of 3exptime. it also shows that the full class of concurrent parity games is no harder than the special case of turn-based stochastic reachability games, for which np &cap; conp is the best known bound.while the previous, more restricted np &cap; conp results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and &epsilon;-optimal strategies (which achieve the value of the game within a parameter &epsilon; > 0) require in general both randomization and infinite memory. hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. first, we show that there exist &epsilon;-optimal strategies that in the limit coincide with memoryless strategies; this parallels the celebrated result of mertens-neyman for concurrent games with limit-average objectives. second, we complete the characterization of the memory requirements for &epsilon;-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for &epsilon;-optimality for cob&uuml;chi conditions.
quantitative stochastic parity games. we study perfect-information stochastic parity games. these are two-player nonterminating games which are played on a graph with turn-based probabilistic transitions. a play results in an infinite path and the conflicting goals of the two players are &omega;-regular path properties, formalized as parity winning conditions. the qualitative solution of such a game amounts to computing the set of vertices from which a player has a strategy to win with probability 1 (or with positive probability). the quantitative solution amounts to computing the value of the game in every vertex, i.e., the highest probability with which a player can guarantee satisfaction of his own objective in a play that starts from the vertex.for the important special case of one-player stochastic parity games (parity markov decision processes) we give polynomial-time algorithms both for the qualitative and the quantitative solution. the running time of the qualitative solution is o(d &middot; m3/2) for graphs with m edges and d priorities. the quantitative solution is based on a linear-programming formulation.for the two-player case, we establish the existence of optimal pure memoryless strategies. this has several important ramifications. first, it implies that the values of the games are rational. this is in contrast to the concurrent stochastic parity games of de alfaro et al.; there, values are in general algebraic numbers, optimal strategies do not exist, and ε-optimal strategies have to be mixed and with infinite memory. second, the existence of optimal pure memoryless strategies together with the polynomial-time solution forone-player case implies that the quantitative two-player stochastic parity game problem is in np &cap; co-np. this generalizes a result of condon for stochastic games with reachability objectives. it also constitutes an exponential improvement over the best previous algorithm, which is based on a doubly exponential procedure of de alfaro and majumdar for concurrent stochastic parity games and provides only ε-approximations of the values.
on the tandem duplication-random loss model of genome rearrangement. we initiate the algorithmic study of a new model of genome rearrangement, the tandem duplication-random loss model, in which a genome evolves via successive rounds of tandem duplication of a contiguous segment of genes, followed by the loss of one copy of each of the duplicated genes. this model is well-known in the evolutionary biology literature, where it has been used to explain many of the known rearrangements in vertebrate mitochondrial genomes. based on the model, we formalize a notion of distance between two genomes and show how to compute it efficiently for two interesting regions of the parameter space. we then consider median problems (i.e. finding the point which minimizes the sum of distances to a given set of points under some distance function) in the context of maximum parsimony phylogenetic reconstruction for these two special cases. surprisingly, one of them turns out to correspond to the well-known rank aggregation problem, while the other corresponds to the biologically interesting case of whole genome duplication and loss, and we give an o(log log n) additive approximation algorithm for the latter.
embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. in this article, we study metrics of negative type, which are metrics (v, d) such that &sqrt;d is an euclidean metric; these metrics are thus also known as &ell;2-squared metrics. we show how to embed n-point negative-type metrics into euclidean space &ell;2 with distortion d &equals; o(log3/4n). this embedding result, in turn, implies an o(log3/4k)-approximation algorithm for the sparsest cut problem with nonuniform demands. another corollary we obtain is that n-point subsets of &ell;1 embed into &ell;2 with distortion o(log3/4 n).
generating well-shaped delaunay meshed in 3d. a triangular mesh in 3d is a decomposition of a given geometric domain into tetrahedra. the mesh is well-shaped if the aspect ratio of every of its tetrahedra is bounded from above by a constant. it is delaunay if the interior of the circum-sphere of each of its tetrahedra does not contain any other mesh vertices. generating a well-shaped delaunay mesh for any 3d domain has been a long term outstanding problem. in this paper, we present an efficient 3d delaunay meshing algorithm that mathematically guarantees the well-shape quality of the mesh, if the domain does not have acute angles. the main ingredient of our algorithm is a novel refinement technique which systematically forbids the formation of shivers, a family of bad elements that none of the previous known algorithms can cleanly remove, especially near the domain boundary &mdash; needless to say, that our algorithm ensure that there is no sliver near the boundary of the domain.