waashk/dblp huggingface dataset:
on the overlay of envelopes in four dimensions. we show that the complexity of the overlay of two envelopes of arrangements of n semi-algebraic surfaces or surface patches of constant description complexity in four dimensions is o(n4-1/&lceil;s/2&rceil;+&epsilon;), for any &epsilon; > 0, where s is a constant related to the maximal degree of the surfaces. this is the first non-trivial (sub-quartic) bound for this problem, and for s = 1, 2 it almost matches the near-cubic lower bound. we discuss several applications of this result, including (i) an improved bound for the complexity of the region enclosed between two envelopes in four dimensions, (ii) an improved bound for the complexity of the space of all hyperplane transversals of a collection of simply-shaped convex sets in 4-space, (iii) an improved bound for the complexity of the space of all line transversals of a similar collection of sets in 3-space, and (iv) improved bounds for the complexity of the union of certain families of objects in four dimensions. the analysis technique we introduce is quite general, and has already proved useful in unrelated contexts.
maintaining significant stream statistics over sliding windows. in this paper, we introduce the significant one counting problem. let &epsilon; and &theta; be respectively some user-specified error bound and threshold. the input of the problem is a stream of bits. we need to maintain some data structure that allows us to estimate the number of 1-bits in a sliding window of size n such that whenever there are at least &theta;n 1-bits in the window, the relative error of the estimate is guaranteed to be at most &epsilon;. when &theta; 1/n, our problem becomes the basic counting problem proposed by datar et al. [acm-siam symposium on discrete algorithms (2002), pp. 635--644]. we prove that any data structure for the significant one counting problem must use at least &omega;(1/&epsilon; log2 1/&theta; + log &epsilon; &theta;n) bits of memory. we also design a data structure for the problem that matches this memory bound and supports constant query and update time. note that for fixed &theta; and &epsilon;, our data structure uses o(log n) bits of memory, while any data structure for the basic counting problem needs &omega;(log2 n) bits in the worst case.
online ascending auctions for gradually expiring items. in this paper we consider online auction mechanisms for the allocation of m items that are identical to each other except for the fact that they have different expiration times, and each item must be allocated before it expires. players arrive at different times, and wish to buy one item before their deadline. the main difficulty is that players act "selfishly" and may mis-report their values, deadlines, or arrival times. we begin by showing that the usual notion of truthfulness (where players follow a single dominant strategy) cannot be used in this case, since any (deterministic) truthful auction cannot obtain better than an m-approximation of the social welfare. therefore, instead of designing auctions in which players should follow a single strategy, we design two auctions that perform well under a wide class of selfish, "semi-myopic", strategies. for every combination of such strategies, the auction is associated with a different algorithm, and so we have a family of "semi-myopic" algorithms. we show that any algorithm in this family obtains a 3-approximation, and by this conclude that our auctions will perform well under any choice of such semi-myopic behaviors. we next turn to provide a game-theoretic justification for acting in such a semi-myopic way. we suggest a new notion of "set-nash" equilibrium, where we cannot pin-point a single best-response strategy, but rather only a set of possible best-response strategies. we show that our auctions have a set-nash equilibrium which is all semi-myopic, hence guarantees a 3-approximation. we believe that this notion is of independent interest.
a group-strategyproof mechanism for steiner forests. in this paper we design an approximately budget-balanced and group-strategyproof cost-sharing mechanism for the steiner forest game. an instance of this game consists of an undirected graph g = (v, e), non-negative costs ce for all edges e &isin; e, and a set r &sube; v x v of k terminal pairs. each terminal pair (s, t) &isin; r is associated with an agent that wishes to establish a connection between nodes s and t in the underlying network. a feasible solution is a forest f that contains an s, t-path for each connection request (s, t) &isin; r.previously, jain and vazirani [4] gave a 2-approximate budget-balanced and group-strategyproof cost-sharing mechanism for the steiner tree game --- a special case of the game considered here. such a result for steiner forest games has proved to be elusive so far, in stark contrast to the well known primal-dual (2 -- 1/k)-approximate algorithms [1, 2] for the problem.the cost-sharing method presented in this paper is 2-approximate budget-balanced and this is tight with respect to the budget-balance factor.our algorithm is an original extension of known primal-dual methods for steiner forests [1]. an interesting byproduct of the work in this paper is that our steiner forest algorithm is (2 -- 1/k)-approximate despite the fact that the forest computed by our method is usually costlier than those computed by known primal-dual algorithms. in fact the dual solution computed by our algorithm is infeasible but we can still prove that its total value is at most the cost of a minimum-cost steiner forest for the given instance.
trees and markov convexity. we give combinatorial, geometric, and probabilistic characterizations of the distortion of tree metrics into lp spaces. this requires the development of new embedding techniques, as well as a method for proving distortion lower bounds which is based on the wandering of markov chains in banach spaces, and a new metric invariant we call markov convexity. trees are thus the first non-trivial class of metric spaces for which one can give a simple and complete characterization of their distortion into a hilbert space, up to universal constants. our results also yield an efficient algorithm for constructing such embeddings.
distributions of points in the unit-square and large -gons. we consider a generalization of heilbronn's triangle problem by asking, given any integers n>=k, for the supremum @d"k(n) of the minimum area determined by the convex hull of some k of n points in the unit square [0,1]^2, where the supremum is taken over all distributions of n points in [0,1]^2. improving the lower bound @d"k(n)=@w(1/n^(^k^-^1^)^/^(^k^-^2^)) from [c. bertram-kretzberg, t. hofmeister, h. lefmann, an algorithm for heilbronn's problem, siam journal on computing 30 (2000) 383-390] and from [w.m. schmidt, on a problem of heilbronn, journal of the london mathematical society (2) 4 (1972) 545-550] for k=4, we show that @d"k(n)=@w((logn)^1^/^(^k^-^2^)/n^(^k^-^1^)^/^(^k^-^2^)) for fixed integers k>=3 as asked for in [c. bertram-kretzberg, t. hofmeister, h. lefmann, an algorithm for heilbronn's problem, siam journal on computing 30 (2000) 383-390]. moreover, we provide a deterministic polynomial time algorithm which finds n points in [0,1]^2, which achieve this lower bound on @d"k(n).
complexity classification of network information flow problems. we address the network information flow problem, in which messages available to a set of sources must be passed through a network to a set of sinks with specified demands. this differs from traditional multicommodity flow, because information can be duplicated and encoded. previous work has focused on the special case of multicasting using linear coding. in this paper, we explore the applicability of network coding to a breadth of problems and consider the greater potential of nonlinear coding techniques. our main contribution is a taxonomy of network information flow problems. we establish a three-way partition consisting of problems solvable without resorting to network coding, problems requiring network coding that are polynomial-time solvable, and problems for which obtaining a linear network coding solution is np-hard. we also demonstrate limitations of linear coding: for multicasting, nonlinear codes may employ a smaller alphabet than any linear code and, more generally, there exist solvable information flow problems that do not admit a linear solution.
on approximating the achromatic number. the achromatic number problem is to legally color the vertices of an input graph with the maximum number of colors, denoted &psgr;*, so that every two color classes share at least one edge. this problem is known to be np-hard. for general graphs we give an algorithm that approximates the achromatic number within ratio of &ogr;(n &middot;log log n/ log n). this improves over the previously known approximation ratio of &ogr;(n/&radic;log n), due to chaudhary and vishwanathan [4]. for graphs of girth at least 5 we give an algorithm with approximation ratio &ogr;(min{n1/3, &radic;&psgr;*}). this improves over an approximation ratio &ogr;(&radic;&psgr;*) = &ogr;(n3/8) for the more restricted case of graphs with girth at least 6, due to krista and lorys [13]. we also give the first hardness result for approximating the achromatic number. we show that for every fixed &isin; > 0 there in no 2 - &isin; approximation algorithm, unless p = np.
network coding: does the model need tuning? we consider the general network information flow problem, which was introduced by ahlswede et. al[1]. we show a periodicity effect: for every integer m &ge; 2, there exists an instance of the network information ow problem that admits a solution if and only if the alphabet size is a perfect mth power. building on this result, we construct an instance with o(m) messages and o(m) nodes that admits a solution if and only if the alphabet size is an enormous 2exp(&omega;(m1/3)). in other words, if we regard each message as a length-k bit string, then k must be exponential in the size of the network. for this same instance, we show that if edge capacities are slightly increased, then there is a solution with a modest alphabet size of o(2m). in light of these results, we suggest that a more appropriate model would assume that the network operates at slightly under capacity.
generating low-degree 2-spanners. a k-spanner of a connected graph g = (v,e) is a subgraph g\spr consisting of all the vertices of v and a subset of the edges, with the additional property that the distance between any two vertices in g\spr is larger than that distance in g by no more than a factor of k. this paper concerns the problem of finding a 2-spanner in a given graph, with minimum maximum degree. a randomized approximation algorithm is provided for this problem, with approximation ration of [o\tilde](d1/4).
approximation algorithms for grammar-based compression. several recently-proposed data compression algorithms are based on the idea of representing a string by a context-free grammar. most of these algorithms are known to be asymptotically optimal with respect to a stationary ergodic source and to achieve a low redundancy rate. however, such results do not reveal how effectively these algorithms exploit the grammar-model itself; that is, are the compressed strings produced as small as possible? we address this issue by analyzing the approximation ratio of several algorithms, that is, the maximum ratio between the size of the generated grammar and the smallest possible grammar over all inputs. on the negative side, we show that every polynomial-time grammar-compression algorithm has approximation ratio at least 8569/8568 unless p = np. moreover, achieving an approximation ratio of o(log n/log log n) would require progress on an algebraic problem in a well-studied area. we then upper and lower bound approximation ratios for the following four previously-proposed grammar-based compression algorithms: sequential, bisection, greedy, and lz78, each of which employs a distinct approach to compression. these results seem to indicate that there is much room to improve grammar-based compression algorithms.
complete partitions of graphs. a complete partition of a graph g is a partition of v(g) such that any two classes are connected by an edge. let cp(g) denote the maximum number of classes in a complete partition of g. this measure was defined in 1969 by gupta [18], and is known to be np-hard on several classes of graphs. we obtain the first, and essentially tight, lower and upper bounds on the approximability of this problem. we show that there is a randomized polynomial-time algorithm that given a graph g produces a complete partition of size &omega;(cp(g)/&radic;lg|v(g)|). this algorithm can be derandomized.we show that the upper bound is essentially tight: there is a constant c > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph g with n vertices produces a complete partition into at least c cp(g)/&radic;lg n classes, then np &sube; rtime(no(lg lg n)). the problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form &theta;((lg n)c) for some constant c strictly between 0 and 1.
on-line randomized call control revisited. we consider the problem of on-line call admission and routing on trees and meshes. previous work gave randomized on-line algorithms for these problems and proved that they have optimal (up to constant factors) competitive ratios. however, these algorithms can obtain very low profit with high probability. we investigate the question of devising for these problems on-line competitive algorithms that also guarantee a "good" solution with "good" probability.we give a new family of randomized algorithms with asymptotically optimal competitive ratios and "good" probability to get a profit close to the expectation. we complement these results by providing bounds on the probability of any optimally competitive randomized on-line algorithm for the problems we consider to get a profit close to the expectation. to the best of our knowledge, this is the first study of the relationship between the tail distribution and the competitive ratio of randomized on-line benefit algorithms.
analysis of a local search heuristic for facility location problems. in this paper, we study approximation algorithms for several np-hard facility location problems. we prove that a simple local search heuristic yields polynomial-time constant-factor approximation bounds for the metric versions of the uncapacitated k-median problem and the uncapacitated facility location problem. (for the k-median problem, our algorithms require a constant-factor blowup in the parameter k.) this local search heuristic was first proposed several decades ago, and has been shown to exhibit good practical performance in empirical studies. we also extend the above results to obtain constant-factor approximation bounds for the metric versions of capacitated k-median and facility location problems.
placement algorithms for hierarchical cooperative caching. consider a hierarchical network in which each node periodically issues a request for an object drawn from a fixed set of unit-sized objects. suppose further that the following conditions are satisfied: the frequency with which each node accesses each object is known; each node has a cache of known capacity; any cache can be accessed by any node; any request is satisfied by the closest node with a copy of the desired object. in such an environment, it is desirable to fill the available cach space with copies of objects in such a way that the average access cost is minimized. we provide both exact and approximate polynomial-time algorithms for this hierarchical placement problem. our exact algorithm is based on a reduction to min-cost flow, and does not appear to be practical for large problem sizes. thus we are motivated to search for a faster approximation algorithm. our main result is a simple constant-factor approximation algorithm for the hierarchical placement problem that admits an efficient distributed implementation.
property testing of data dimensionality. data dimensionality is a crucial issue in a variety of settings, where it is desirable to determine whether a data set given in a high-dimensional space adheres to a low-dimensional structure. we study this problem in the framework of property testing: given a query access to a data set s, we wish to determine whether s is low-dimensional, or whether it should be modified significantly in order to have the property. allowing a constant probability of error, we aim at algorithms whose complexity does not depend on the size of s.we present algorithms for testing the low-dimensionality of a set of vectors and for testing whether a matrix is of low rank. we then address low-dimensionality in metric spaces. for vectors in the metric space l1, we show that low-dimensionality is not testable. for l2, we show that a data set can be tested for having a low-dimensional structure, but that the property of approximately having such a structure is not testable.
locally satisfiable formulas. a cnf formula &psi; is k-satisfiable if each k clauses of &psi; can be satisfied simultaneously. let &pi;k be the largest real number such that for each k-satisfiable formula with variables xi, there are probabilities pi with the following property: if each variable xi is chosen randomly and independently to be true with the probability pi, then each clause of is satisfied with the probability at least &pi;k.we determine the numbers &pi;k and design a linear-time algorithm which given a formula either outputs that &psi; is not k-satisfiable or finds probabilities pi such that each clause &psi; of is satisfied with the probability at least &pi;k. our approach yields a robust linear-time deterministic algorithm which finds for a k-satisfiable formula a truth assignment satisfying at least the fraction of &pi;k of the clauses.a related parameter is rk which is the largest ratio such that for each k-satisfiable cnf formula with m clauses, there is a truth assignment which satisfies at least rkm clauses. it was known that &pi;k = rk for k = 1, 2, 3. we compute the ratio r4 and show &pi;4 6 = r4. we also design a linear-time algorithm which finds a truth assignment satisfying at least the fraction r4 of the clauses for 4-satisfiable formulas.
a constant approximation algorithm for the one-warehouse multi-retailer problem. deterministic inventory theory provides streamlined optimization models that attempt to capture tradeoffs in managing the flow of goods through a supply chain. we will consider a well-studied inventory model, called the one-warehouse multi-retailer problem (owmr). and give the first approximation algorithm with constant performance guarantee; more specifically, we give a 2.398-approximation algorithm. our results are based on an lp-rounding approach, and hence not only provide good algorithmic results, but show strong integrality gaps for these linear programs. furthermore, we extend this result to obtain a constant performance guarantee for a capacitated variant of this model.
approximating asymmetric maximum tsp. the asymmetric maximum travelling salesman problem, also known as the taxicab ripoff problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with non-negative weights. interesting in its own right, this problem is also motivated by such problems such as the shortest superstring problem.we propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. this (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. our solution uses a simple lp formulation. previous solutions where combinatorial. we make use of the lp in a novel manner and strengthen the path-coloring method originally proposed in [13].
certifying algorithms for recognizing interval graphs and permutation graphs. a certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. the certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. we give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. we show that our certificates of nonmembership can be authenticated in o(|v|) time.
the similarity metric. a new class of metrics appropriate for measuring effective similarity relations between sequences, say one type of similarity per metric, is studied. we propose a new "normalized information distance", based on the noncomputable notion of kolmogorov complexity, and show that it minorizes every metric in the class (that is, it is universal in that it discovers all effective similarities). we demonstrate that it too is a metric and takes values in [0, 1]; hence it may be called the similarity metric. this is a theory foundation for a new general practical tool. we give two distinctive applications in widely divergent areas (the experiments by necessity use just computable approximations to the target notions). first, we computationally compare whole mitochondrial genomes and infer their evolutionary history. this results in a first completely automatic computed whole mitochondrial phylogeny tree. secondly, we give fully automatically computed language tree of 52 different language based on translated versions of the "universal declaration of human rights".
between o(nm) and o(n alpha). this paper uses periodic matrix multiplication to improve the time complexities for a number of graph problems. the time for finding a clique cutset in a graph is reduced from o(nm) to o(n2.69), the time for finding an asteroidal triple is reduced to o(n2.82), and the time for finding a star cutset, a two-pair, and a dominating pair is reduced from o(nm) to o(n2.79).it is also shown that each of these problems is at least as hard as one of three basic graph problems for which the best known algorithms run in time o(nm) and o(n&alpha;).
gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance. the syntenic distance between two genomes is given by the minimum number of fusions, fissions, and translocations required to transform one into the other, ignoring the order of genes within chromosomes. the problem of computing this distance is np-complete. in this paper, we give an &ogr;(2&ogr;(n log n)) algorithm to exactly compute the syntenic distance between two genomes that contain at most n chromosomes. our algorithm requires &ogr;(2&ogr;(d log d)) time when this distance is d, improving the &ogr;(2&ogr;(d2)) running time of the beat previous exact algorithm. our result is based upon a tight connection between syntenic distance and a novel generalization of the classical gossip problem. we define the incomplete gossip problem, in which there are n gossipers who each have a unique piece of initial information. they communicate by phone calls in which the participants exchange all their information, and the goal is to minimize the total number of phone calls necessary to inform each gossiper of his set of relevant gossip which he desires to learn.
the diameter of random massive graphs. many massive graphs (such as the www graph and call graphs) share certain universal characteristics which can be described by so-called the &ldquo;power law&rdquo;. here we determine the diameter of random power law graphs up to a constant factor for almost all ranges of parameters. these results show a strong evidence that the diameters of most massive graphs are about logarithm of their sizes up to a constant factor.