waashk/dblp huggingface dataset:
allocating vertex pi-guards in simple polygons via pseudo-triangulations. we use the concept of pointed pseudo-triangulations to establish new upper and lower bounds on a well known problem from the area of art galleries: what is the worst case optimal number of vertex &pi;-guards that collectively monitor a simple polygon with n vertices?our results are as follows:1. any simple polygon with n vertices can be mon- itored by at most [n/2] general vertex &pi;-guards. this bound is tight up to an additive constant of 1.2. any simple polygon with n vertices, k of which are convex, can be monitored by at most [(2n -- k)/3] edge-aligned vertex &pi;-guards. this is the first non- trivial upper bound for this problem and it is tight for the worst case families of polygons known so far.
erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. there is an error in our paper "an approximation algorithm for minimum-cost vertex-connectivity problems," which appeared in soda '95 [2] (see also the journal version [3]). below we briefly describe the problem and discuss which of our results can be shown to hold.a complete version of our erratum can be found at www.almaden.ibm.com/cs/people/dpw.
the probabilistic method. the use of randomness is now an accepted tool in theoretical computer science but not everyone is aware of the underpinnings of this methodology in combinatorics - particularly, in what is now called the probabilistic method as developed primarily by paul erdo&huml;s over the past half century. here i will explore a particular set of problems - all dealing with &ldquo;good&rdquo; colorings of an underlying set of points relative to a given family of sets. a central point will be the evolution of these problems from the purely existential proofs of erdo&huml;s to the algorithmic aspects of much interest to this audience.
new approaches to covering and packing problems. covering and packing integer programs model a large family of combinatorial optimization problems. the current-best approximation algorithms for these are an instance of the basic probabilistic method: showing that a certain randomized approach produces a good approximation with positive probability. this approach seems inherently sequential; by employing the method of alteration we present the first rnc and nc approximation algorithms that match the best sequential guarantees. extending our approach, we get the first rnc and nc approximation algorithms for certain multi-criteria versions of these problems. we also present the first nc algorithms for two packing and covering problems that are not subsumed by the above result: finding large independent sets in graphs, and rounding fractional group steiner solutions on trees.
a simple gap-canceling algorithm for the generalized maximum flow problem. we give a simple primal algorithm for the generalized maximum flow problem that repeatedly finds and cancels generalized augmenting paths (gaps). we use ideas of wallacher [26] to find gaps that have a good trade-off between the gain of the gap and the residual capacity of its arcs; our algorithm may be viewed as a special case of wayne's algorithm for the generalized minimum-cost circulation problem [27]. most previous algorithms for the generalized maximum flow problem are dual-based; the few previous primal algorithms (including wayne [27]) require subroutines to test the feasibility of linear programs with two variables per inequality (tvpis). we give an o(mn) time algorithm for finding negative-cost gaps which can be used in place of the tvpi tester. this yields an algorithm with o(m log (mb&epsilon;)) iterations of o(mn) time to compute an &epsilon;-optimal flow, or o(m2 log(mb)) iterations to compute an optimal flow, for an overall running time of o(m3n log(mb)). the fastest known running time for this problem is &otilde;(m2n log b), and is due to radzik [22], building on earlier work of goldfarb, jin, and orlin [14].
finding the repeated median regression line. the repeated median regression line is a robust regression estimate, having a maximal 50% breakdown point. this paper presents an o(n(log n)2) algorithm for finding the repeated median regression line through n points in the plane.
correlation clustering: maximizing agreements via semidefinite programming. we consider the correlation clustering problem introduced in [2]. given a graph g = (v,e) where each edge is labeled either "+" (similar) or "-" (different), we want to cluster the nodes so that the + edges lie within the clusters and the -- edges lie between clusters. specifically, we want to maximize agreements --- the number of + edges within clusters and -- edges between clusters. this problem is np-hard [2]. we give a 0.7666-approximation algorithm for maximizing agreements on any graph even when the edges have non-negative weights (along with labels) and we want to maximize the weight of agreements. these were posed as open problems in [2]. previously the only results known were a trivial 0.5-approximation for arbitrary edge weighted graphs, and a ptas with unit edge weights when |e| = &omega;(|v|2). somewhat surprisingly, our algorithm always produces a clustering with at most 6 clusters. as a corollary we get a 0.7666-approximation algorithm for the k-clustering variant of the problem where we may create at most k clusters. a major component of this algorithm is a simple, easy-to-analyze algorithm that by itself achieves an approximation ratio of 0.75, opening at most 4 clusters.
fault-tolerant facility location. we consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has a requirement that rj distinct facilities serve it, instead of just one. we give a 2.076-approximation algorithm for this problem using lp rounding, which is currently the best-known performance guarantee. our algorithm exploits primal and dual complementary slackness conditions and is based on clustered randomized rounding. a technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. for the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm. we also consider a fault-tolerant version of the k-median problem. in the metric k-median problem, we are given n points in a metric space. we must select k of these to be centers, and then assign each input point j to the selected center that is closest to it. in the fault-tolerant version we want j to be assigned to rj distinct centers. the goal is to select the k centers so as to minimize the sum of assignment costs. the primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant k-median problem for this case. this the first constant-factor approximation algorithm for the uniform requirements case.
(un)expected behavior of typical suffix trees. suffix tree is a data structure widely used in algorithms on words and data compression. despite this, very little is known about its typical behavior. recently, chang and lawler have designed a sublinear expected time algorithm for approximate string matching using simple estimates of some parameters of suffix trees. it seems that any further advances in such an endover are subject to better understanding of suffix trees behavior. in this paper, we use a novel technique called string ruler approach to provide a characterization of several basic parameters of suffix trees (dependency among symbols are allowed !). these findings are used to :(i) settle in the negative the conjecture of wyner and ziv regarding the typical behavior of the universal data compression scheme of lampel and ziv; (ii) prove an open problem regarding the length of a block in the lampel-ziv parsing algorithm; (iii) provide new insights and generalizations of string matching algorithms, particularly the one by chang and lawler.
self-adjusting top trees. the dynamic trees problem is that of maintaining a forest that changes over time through edge insertions and deletions. we can associate data with vertices or edges, and manipulate this data individually or in bulk, with operations that deal with whole paths or trees. efficient solutions to this problem have numerous applications, particularly in algorithms for network flows and dynamic graphs in general. several data structures capable of logarithmic-time dynamic tree operations have been proposed. the first was sleator and tarjan's st-tree [16, 17], which represents a partition of the tree into paths. although reasonably fast in practice, adapting st-trees to different applications is nontrivial. topology trees [9], top trees [3], and rc-trees [1] are based on tree contractions: they progressively combine vertices or edges to obtain a hierarchical representation of the tree. this approach is more flexible in theory, but all known implementations assume the trees have bounded degree; arbitrary trees are supported only after ternarization. we show how these two approaches can be combined (with very little overhead) to produce a data structure that is as generic as any other, very easy to adapt, and as practical as st-trees.
design of on-line algorithms using hitting times. random walks are well known for playing a crucial role in the design of randomized off-line as well as on-line algorithms. in this work we prove some basic identities for ergodic markov chains (e.g., an interesting characterization of reversibility in markov chains is obtained in terms of first passage times). besides providing new insight into random walks on weighted graphs, we show how these identities give us a way of designing competitive randomized on-line algorithms for certain well-known problems.
quick and good facility location. we consider the facility location problem with shortest path distances in a weighted graph. w.h.p., we get an approximation factor of 1.62 in o(n + m) time with n and m the number of nodes and edges. also, as a kind of warm-up, for a metric with a constant-times distance oracle, we get the factor 1.62 deterministically in o(n2 log n) time.our results build on a recent facility location algorithm of jain, mahdian, and saberi (stoc'02) achieving an approximation factor of 1.61 in o(n3) time.
on ac implementations of fusion trees and atomic heaps. addressing a question of fredman and willard from stoc'90, we show that fusion trees cannot be implemented using the ac0 operations available through a standard programming language such as c. however, they can be implemented using ac0 operations on emerging multimedia processors such as the pentium 4.a fusion node is a linear space representation of an integer set x of size o(&radic;w), where w &ge; log n is the word-length. the fusion node supports searches in x in constant time. here, a search for y in x returns max{x &epsilon; x&verbar;x &le; y}. using fusion nodes in a o(&radic;w)-degree fusion tree gave fredman and willard o(log n/log w) searching for general n, beating the comparison based lower-bound. however, the search routine uses multiplication which is not an ac0 operation.fredman and willard asked if multiplication instructions could be avoided. we show that the answer is "no" unless you have room for a multiplication table. more precisely, restricting ourselves to the ac0 operations available through c, we show that constant time look-ups or searches in sets of any non-constant size require space 2&omega;(w). however, if we have that much space, i.e., 2&epsilon;w for some constant &epsilon; > 0, then we can tabulate multiplication of (&epsilon;w/2)-bit numbers, and then we get constant time multiplication of words using additions and shifts. previous related lowerbounds all disallowed some common ac0 instructions in c such as shifts.we note that even on the weaker "practical ram" the above 2&omega;(w) space lower-bound for constant look-ups was only known for sets of size &omega;(w2) (miltersen, icalp'96). our &omega;(1) set size is best possible since sets of constant size can be searched directly in constant time.contrasting the above result, we show that using the ac0 operations available on intel's new pentium 4, we can implement both fusion trees and fredman and willard's later atomic heaps from focs'90. among the many consequences, we get linear time and space ac0 implementations of minimum spanning tree and undirected single source shortest paths. also, we get optimal &theta;(log n/log log n) implementations of dynamic rank and 1&frac12; dimensional range searching. previous optimal solutions required either multiplication or the use of self-designed ac0 instructions not available on existing processors.
on ram priority queues. priority queues are some of the most fundamental data structures. for example, they are used directly for task scheduling in operating systems. moreover, they are essential to greedy algorithms. we study the complexity of integer priority queue operations on a ram with arbitrary word size, modeling the possibilities in standard imperative programming languages such as c. we present exponential improvements over previous bounds, and we show tight relations to sorting.our first result is a ram priority queue supporting find-min in constant time and insert and delete-min in time o(log log n), where n is the current number of keys in the queue. this is an exponential improvement over the $o(\sqrt{\log n})$ bound of fredman and willard [ proceedings of the 22nd acm symposium on the theory of computing, baltimore, md, pp. 1--7]. plugging this priority queue into dijkstra's algorithm gives an o(mlog log m) algorithm for the single source shortest path problem on a graph with m edges, as compared with the previous $o(m\sqrt{\log m})$ bound based on fredman and willard's priority queue. the above bounds assume $o(n 2^{{\varepsilon} w})$ space, where w is the word length and ${\varepsilon}>0$. they can, however, be achieved in linear space using randomized hashing.our second result is a general equivalence between sorting and priority queues. a priority queue is monotone if the minimum is nondecreasing over time, as in many greedy algorithms. we show that on a ram, the amortized operation cost of a monotone priority queue is equivalent to the per-key cost of sorting. for example, the equivalence implies that the single source shortest paths problem on a graph with m edges is no harder than that of sorting m keys. with the current ram sorting, this gives an o(m log log m) time bound, as above, but the relation holds regardless of the future developments in ram sorting.from the equivalence result, for any fixed ${\varepsilon}>0$, we derive a randomized monotone $o(\sqrt{\log n}^{1+{\varepsilon}})$ priority queue with expected constant time decrease-key. plugging this into dijkstra's algorithm gives an $o(n\sqrt{\log n}^{1+{\varepsilon}}+m)$ algorithm for the single source shortest path problem on a graph with n nodes and m edges, complementing the above o(mlog log m) algorithm if $m\gg n$. this improves the o(nlog n/log log n + m) bound by fredman and willard [proceedings of the 31st ieee symposium on the foundations of computer science, st. louis, mo, 1990, pp. 719--725], based on their o(log n/log log n) priority queue with constant decrease-key.
tabulation based 4-universal hashing with applications to second moment estimation. we show that 4-universal hashing can be implemented efficiently using tabulated 4-universal hashing for characters, gaining a factor of 5 in speed over the fastest existing methods. we also consider generalization to k-universal hashing, and as a prime application, we consider the approximation of the second moment of a data stream.
spanners and emulators with sublinear distance errors. let k &ge; 2 be an integer. we show that any undirected and unweighted graph g = (v, e) on n vertices has a subgraph g' = (v, e') with o(kn1+1/k) edges such that for any two vertices u, v &isin; v, if &delta;g(u, v) = d, then &delta;g'(u, v) = d+o(d1-1/k-1). furthermore, we show that such subgraphs can be constructed in o(mn1/k) time, where m and n are the number of edges and vertices in the original graph. we also show that it is possible to construct a weighted graph g* = (v, e*) with o(kn1+1/(2k-1)) edges such that for every u, v &isin; v, if &delta;g(u, v) = d, then &delta; &le; &delta;g*(u, v) = d + o(d1-1/k-1). these are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated.
efficient algorithms for the hitchcock transportation problem. we consider the hitchcock transportation problem on n supply points and k demand points when n is much greater than k. the problem is solved in o(n2k log n + n2 log2 n) time if n > k log k. further, applying a geometric method named splitter finding and randomization, we improve the time complexity for a case in which the ratio c of the least supply and the maximum supply satisfies the inequality log cn < n/k4 log n. indeed, if n < k5 log3 k and c = poly(n), the problem is solved in o(kn) time, which is optimal.
binary space partitions for line segments with a limited number of directions. we show that there is always a binary space partition (bsp) of size o(n log k) and an autopartition of size o(nk) for n disjoint line segments in the plane, assuming that the segments have k distinct orientations. in particular, if k is a constant, these bounds imply that there is a linear-size bsp and autopartition. our proof is constructive and can be turned into algorithms computing such a bsp or autopartition in o(n2) and o(n2k) times.
confronting hardness using a hybrid approach. a hybrid algorithm is a collection of heuristics, paired with a polynomial time selector s that runs on the input to decide which heuristic should be executed to solve the problem. hybrid algorithms are of particular interest in scenarios where the selector must decide between heuristics that are "good" with respect to different complexity measures.we focus on hybrid algorithms with a "hardness-defying" property: for a problem ii, there is a set of complexity measures {mi} whereby ii is known or conjectured to be unsolvable for each mi, but for each heuristic hi of the hybrid algorithm, one can give a complexity guarantee for hi on the instances of ii that s selects for hi that is strictly better than mi. more concretely, we show that for several np-hard problems, a given instance can either be solved exactly with substantially improved runtime (e.g. 2o(n)), or be approximated in polynomial time with an approximation ratio exceeding that of the known or conjectured inapproximability of the problem, assuming p &ne; np.
instability of fifo in the permanent sessions model at arbitrarily small network loads. we show that for any r > 0, there is a network of first-in-first-out servers and a fixed set of sessions such that: &mdash;the network load is r with respect to the permanent sessions model with bounded arrivals. &mdash;the network can be made unstable.
approximation schemes for metric bisection and partitioning. we design polynomial time approximation schemes (ptass) for metric bisection, i.e. dividing a given finite metric space into two halves so as to minimize or maximize the sum of distances across the cut. the method extends to partitioning problems with arbitrary size constraints. our approximation schemes depend on a hybrid placement method and on a new application of linearized quadratic programs.
primal-dual approach for directed vertex connectivity augmentation and generalizations. in their seminal paper, frank and jord&aacute;n &lsqb;1995&rsqb; show that a large class of optimization problems, including certain directed graph augmentation, fall into the class of covering supermodular functions over pairs of sets. they also give an algorithm for such problems, however, it relies on the ellipsoid method. prior to our result, combinatorial algorithms existed only for the 0--1 valued problem. our key result is a combinatorial algorithm for the general problem that includes directed vertex or s&minus;t connectivity augmentation. the algorithm is based on bencz&uacute;r's previous algorithm for the 0--1 valued case &lsqb;bencz&uacute;r 2003&rsqb;. our algorithm uses a primal-dual scheme for finding covers of partially ordered sets that satisfy natural abstract properties as in frank and jord&aacute;n. for an initial (possibly greedy) cover, the algorithm searches for witnesses for the necessity of each element in the cover. if no two (weighted) witnesses have a common cover, the solution is optimal. as long as this is not the case, the witnesses are gradually exchanged for smaller ones. each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest-path manner to obtain a solution of size one less.
approximating the minimum strongly connected subgraph via a matching lower bound. we present a 3/2-approximation algorithm for the problem of finding a minimum strongly connected spanning subgraph in a given directed graph. as a corollary we obtain a 3/2-approximation algorithm for the more general minimum equivalent digraph problem. the performance of our algorithm is measured against a lower bound obtained from a simple matching problem. the performance guarantee is optimal with respect to the lower bound.
distribution sort with randomizing cycle. parallel independent disks can enhance the performance of external memory (em) algorithms, but the programming task is often difficult. in this paper we develop randomized variants of distribution sort for use with parallel independent disks. we propose a simple variant called randomized cycling distribution sort (rcd) and prove that it has optimal expected i/o complexity. the analysis uses a novel reduction to a model with significantly fewer probabilistic interdependencies. experimental evidence is provided to support its practicality. other simple variants are also examined experimentally and appear to offer similar advantages to rcd. based upon ideas in rcd we propose general techniques that transparently simulate algorithms developed for the unrealistic multihead disk model so that they can be run on the realistic parallel disk model. the simulation is optimal for two important classes of algorithms; the class of multipass algorithms, which make a complete pass through their data before accessing any element a second time, and the algorithms based upon the well-known distribution paradigm of em computation.
predicting the "unpredictable". this is a survey of results about the accuracy of prediction when the predictor has no prior knowledge about the process that s/he must forecast. no prior knowledge means just that; no moments, distributions, periods etc.for example, suppose one is asked to predict successive outcomes of an infinite sequence of 0's and 1's. accuracy will be measured by the fraction of correct guesses. with no information beyond this, how well can one guarantee to do?predicting the actual outcome is demanding and in many cases inappropriate; think for example of the case when the sequence is generated by a stochastic process. in this case it is more natural to ask for a probability forecast. how should one measure the error of a probability forecast? given this measure, are there forecasting algorithms that guarantee a small error no matter what process generates the sequence?
on the rectilinear crossing number of complete graphs. we prove a lower bound of 0.3288(n4) for the rectilinear crossing number cr(kn>) of a complete graph on n vertices, or in other words, for the minimum number of convex quadrilaterals in any set of n points in general position in the euclidean plane. as we see it, the main contribution of this paper is not so much the concrete numerical improvement over earlier bounds, as the novel method of proof, which is not based on bounding cr(kn>) for some small n.