waashk/dblp huggingface dataset:
a faster distributed protocol for constructing a minimum spanning tree. this paper studies the problem of constructing a minimum-weight spanning tree (mst) in a distributed network. this is one of the most important problems in the area of distributed computing. there is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time o(&and;(g) + &radic;n log* n) due to kutten and peleg [kp95], where &and;(g) denotes the diameter of the graph g. peleg and rubinovich [pr99] have shown that (&radic;n) time is required for constructing mst even on graphs of small diameter, and claimed that their result "establishes the asymptotic near-optimality" of the protocol of [kp95].in this paper we refine this claim, and devise a protocol that constructs the mst in &otilde;(&mu;(g = w + &radic;n) rounds, where &mu;(g,&mu;) is the mst-radius of the graph. the ratio between the diameter and the mst-radius may be as large as &theta;(n), and, consequently, on some inputs our protocol is faster than the protocol of [kp95] by a factor of (&radic;n). also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [kp95].as part of our protocol for constructing an mst, we develop a protocol for constructing neighborhood covers with a drastically improved running time. the latter result may be of independent interest.
improved schedule for radio broadcast. we show that for every radio network g = (v, e) and source s &epsilon; v, there exists a radio broadcast schedule for g of length rad(g, s) + o(&radic; rad(g, s). log2 n) = o(rad(g, s) + log4 n), where rad(g, s) is the radius of the radio network g with respect to the source s. this result improves the previously best-known upper bound of o(rad(g, s)+log5 n) due to gaber and mansour [12].for graphs with small genus, particularly for planar graphs, we provide an even better upper bound of rad(g, s) + o(&radic; rad(g, s). log n + log3 n) = o(rad(g, s) + log3 n).
frugality in path auctions. we consider the problem of picking (buying) an inexpensive s -- t path in a graph where edges are owned by independent (selfish) agents, and the cost of an edge is known to its owner only. we study the problem of finding frugal mechanisms for this task, i.e. we investigate the payments the buyer must make in order to buy a path.first, we show that any mechanism with (weakly) dominant strategies (or, equivalently, any truthful mechanism) for the agents can force the buyer to make very large payments. namely, for every such mechanism, the buyer can be forced to pay c(p) + 1/2k(c(q) -- c(p)), where c(p) is the cost of the shortest path, c(q) is the cost of the second-shortest path, and k is the number of edges in p. this extends the previous work of archer and tardos [1], who showed a similar lower bound for a subclass of truthful mechanisms called min-function mechanisms. our lower bounds have no such limitations on the mechanism.motivated by this lower bound, we study mechanisms for this problem providing bayes-nash equilibrium strategies for the agents. in this class, we identify the optimal mechanism with regard to total payment. we then demonstrate a separation in terms of average overpayments between the classical vcg mechanism and the optimal mechanism showing that under various natural distributions of edge costs, the optimal mechanism pays at most logarithmic factor more than the actual cost, whereas vcg pays &radic;k times the actual cost. on the other hand, we also show that the optimal mechanism does incur at least a constant factor overpayment in natural distributions of edge costs. since our mechanism is optimal, this gives a lower bound on all mechanisms with bayes--nash equilibria.
approximating minimum max-stretch spanning trees on unweighted graphs. given a graph g and a spanning tree t of g, we say that t is a tree t-spanner of g if the distance between every pair of vertices in t is at most t times their distance in g. the problem of finding a tree t-spanner minimizing t is referred to as the minimum max-stretch spanning tree (mmst) problem. this paper concerns the mmst problem on unweighted graphs. the problem is known to be np-hard, and the paper presents an o(log n) approximation algorithm for it.
a tight upper bound on the probabilistic embedding of series-parallel graphs. in [6] it is shown that every graph can be probabilistically embedded into a distribution over its spanning trees with expected distortion o(log2 n log log n), narrowing the gap left by [1], where a lower bound of &omega;(log n) is established. this lower bound holds even for the class of series-parallel graphs as proved in [8]. in this paper we close this gap for series-parallel graphs, namely we prove that every n-vertex series-parallel graph can be probabilistically embedded into a distribution over its spanning trees with expected stretch o(log n) for every two vertices. we gain our upper bound by presenting a polynomial time probabilistic algorithm that constructs spanning trees with low expected stretch. this probabilistic algorithm can be derandomized to yield a deterministic polynomial time algorithm for constructing a spanning tree of a given series-parallel graph g, whose communication cost is at most o(log n) times larger than that of g.
derandomized dimensionality reduction with applications. the johnson-lindenstrauss lemma provides a way to map a number of points in high-dimensional space into a low-dimensional space, with only a small distortion of the distances between the points. the proofs of the lemma are non-constructive: they show that a random mapping induces small distortions with high probability, but they do not construct the actual mapping. in this paper, we provide a procedure that constructs such a mapping deterministically in time almost linear in the number of distances to preserve times the dimension of the original space. we then use that result (together with nisan's pseudorandom generator) to obtain an efficient derandomization of several approximation algorithms based on semidefinite programming.
harmonic broadcasting is optimal. harmonic broadcasting was introduced by juhn and tseng as a way to reduce the bandwidth requirements required for video-on-demand broadcasting. in this paper, we note that harmonic broadcasting is actually a special case of the priority encoded transmission scheme introduced by albanese et al. and prove---using an information theoretic argument---that it is impossible to achieve the design goals of harmonic broadcasting using a shorter encoding.
parallel processor scheduling with delay constraints. we consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. precedence constraints impose a partial order on the jobs, and both communication and precedence delays impose relative timing constraints on dependent jobs. the combination of these two types of timing constraints naturally models the instruction scheduling problem that occurs during software compilation for state-of-the-art vliw (very long instruction word) processors and multiprocessor parallel machines. we present the first known polynomial-time algorithm for the case where the precedence constraint graph is a forest of in-trees (or a forest of out-trees), the number of machines m is fixed, and the delays (which are a function of both the job pair and the machines on which they run) are bounded by a constant d. our algorithm relies on a new structural theorem for scheduling jobs with arbitrary precedence constraints. given an instance with many independent dags, the theorem shows how to convert, in linear time, a schedule s for only the largest dags into a complete schedule that is either optimal or has the same makespan as s.
improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. we consider worst case time bounds for np-complete problems including 3-sat, 3-coloring, 3-edge-coloring, and 3-list-coloring. our algorithms are based on a constraint satisfaction (csp) formulation of these problems; 3-sat is equivalent to (2, 3)-csp while the other problems above are special cases of (3, 2)-csp. we give a fast algorithm for (3, 2)-csp and use it to improve the time bounds for solving the other problems listed above. our techniques involve a mixture of davis-putnam-style backtracking with more sophisticated matching and network flow based ideas.
dynamic generators of topologically embedded graphs. we provide a data structure for maintaining an embedding of a graph on a surface (represented combinatorially by a permutation of edges around each vertex) and computing generators of the fundamental group of the surface, in amortized time o(log n + log g(log log g)3) per update on a surface of genus g; we can also test orientability of the surface in the same time, and maintain the minimum and maximum spanning tree of the graph in time o(log n + log4 g) per update. our data structure allows edge insertion and deletion as well as the dual operations; these operations may implicitly change the genus of the embedding surface. we apply similar ideas to improve the constant factor in a separator theorem for low-genus graphs, and to find in linear time a tree-decomposition of low-genus low-diameter graphs.
quasiconvex analysis of backtracking algorithms. we consider a class of multivariate recurrences frequently arising in the worst case analysis of davis-putnam-style exponential time backtracking algorithms for np-hard problems. we describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. we develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.
testing bipartiteness of geometric intersection graphs. we show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of balls in rd, in time o(n log n). more generally we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. for unit balls in rd, connectivity testing has equivalent randomized complexity to construction of euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as hopcroft's problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. for line segments or planar disks, testing k-colorability of intersection graphs for k > 2 is np-complete.
all maximal independent sets and dynamic dominance for sparse graphs. we describe algorithms, based on avis and fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. for bounded degree graphs, our algorithms take constant time per set generated; for minor-closed graph families, the time is o(n) per set, and for more general sparse graph families we achieve subquadratic time per set. we also describe new data structures for maintaining a dynamic vertex set s in a sparse or minor-closed graph family, and querying the number of vertices not dominated by s; for minor-closed graph families the time per update is constant, while it is sublinear for any sparse graph family. we can also maintain a dynamic vertex set in an arbitrary m-edge graph and test the independence of the maintained set in time o(&radic;m) per update. we use the domination data structures as part of our enumeration algorithms.
approximating the minimum weight triangulation. in o(n log n) time we compute a triangulation with o(n) new points, and no obtuse triangles, that has length within a constant factor of the minimum possible. we also approximate the minimum weight steiner triangulation using triangulations with no sharp angles. no previous polyonomial time triangulation achieved an approximation factor better than o(log n).
new algorithms for minimum area -gons. given a set p of n points in the plane, we wish to find a set q &sub; p of k points for which the convex hull conv(q> has the minimum area. we solve this, and the related problem of finding a minimum area convex k-gon, in time o(n2 log n) for fixed k, almost matching known bounds for the minimum area triangle problem. our algorithm is based on finding a certain number of nearest vertical neighbors to each line segment determined by two input points. we use a classical result of ramsey theory to prove that these nearest neighbors suffice to determine the minimum convex k-gon.
fast hierarchical clustering and other applications of dynamic closest pairs. we develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. based on a technique previously used by the author for euclidean closest pairs, we show how to insert and delete objects from an <i>n</i>-object set, maintaining the closest pair, in <i>o</i>(<i>n</i> log<sup>2</sup> <i>n</i>) time per update and <i>o</i>(<i>n</i>) space. with quadratic space, we can instead use a quadtree-like structure to achieve an optimal time bound, <i>o</i>(<i>n</i>) per update. we apply these data structures to hierarchical clustering, greedy matching, and tsp heuristics, and discuss other potential applications in machine learning, gröbner bases, and local improvement algorithms for partition and placement problems. experiments show our new methods to be faster in practice than previously used heuristics.
internet packet filter management and rectangle geometry. we consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an action. a given packet should be handled by the action from the maximum priority rule that matches its source and destination. we describe new data structures for quickly finding the rule matching an incoming packet, in near-linear space, and a new algorithm for determining whether a rule set contains any conflicts, in time &ogr;(n3/2).
fast approximation of centrality. social studies researchers use graphs to model group activities in social networks. an important property in this context is the centrality of a vertex: the inverse of the average distance to each other vertex. we describe a randomized approximation algorithm for centrality in weighted graphs. for graphs exhibiting the small world phenomenon, our method estimates the centrality of all vertices with high probability within a (1 + &isin;) factor in near-linear time.
optimal online bounded space multidimensional packing. we solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. to achieve this, we introduce a new technique for classifying the items to be packed. we show that our algorithm is optimal among bounded space algorithms for any dimension d > 1. its asymptotic performance ratio is (ii&infin;)d, where ii&infin; &asymp; 1:691 is the asymptotic performance ratio of the one-dimensional algorithm harmonic. a modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. its asymptotic performance ratio is sublinear in d.additionally, for the special case of packing squares in two-dimensional bins, we present a new unbounded space online algorithm with asymptotic performance ratio of at most 2.271. we also present an approximation algorithm for the offline problem with approximation ratio of 16/11.
lower bounds for external algebraic decision trees. we propose a natural extension of algebraic decision trees to the external-memory setting, where the cost of disk operations overwhelms cpu time, and prove a tight lower bound of &omega;(n logm n) on the complexity of both sorting and element uniqueness in this model of computation. we also prove a &omega;(min{n logm n, n}) lower bound for both problems in a less restrictive model, which requires only that the worst-case internal-memory computation time is finite. standard reductions immediately generalize these lower bounds to a large number of fundamental computational geometry problems.
greedy optimal homotopy and homology generators. we describe simple greedy algorithms to construct the shortest set of loops that generates either the fundamental group (with a given basepoint) or the first homology group (over any fixed coefficient field) of any oriented 2-manifold. in particular, we show that the shortest set of loops that generate the fundamental group of any oriented combinatorial 2-manifold, with any given basepoint, can be constructed in o(n log n) time using a straightforward application of dijkstra's shortest path algorithm. this solves an open problem of colin de verdi&egrave;re and lazarus.
np-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. we consider the version of broadcast scheduling where a server can transmit w messages of a given set at each time-step, answering previously made requests for these messages. the goal is to minimize the average response time (art) if the amount of requests is known in advance for each time-step and message. we prove that this problem is np-hard, thus answering an open question stated by kalyanasundaram, pruhs and velauthapillai (proceedings of esa 2000, lncs 1879, 2000, pp. 290---301). furthermore, we present an approximation algorithm that is allowed to send several messages at once. using six channels for transmissions, the algorithm achieves an art that is at least as good as the optimal solution using one channel.from the np-hardness of broadcast scheduling we derive a new inapproximability result of (2 ¿ ¿, 1) for the (congestion, cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary ¿ > 0. the result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity (d max ¿ u min), a case for which an algorithm with ratio (3, 1) was presented by skutella.
polynomial-time approximation schemes for geometric graphs. a disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. for the case that the disk representation is given, we present polynomial-time approximation schemes (ptass) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. these are the first known ptass for np-hard optimization problems on disk graphs. they are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. the ptass for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. they can be extended to intersection graphs of other &ldquo;disk-like&rdquo; geometric objects (such as squares or regular polygons), also in higher dimensions.
structural and algorithmic aspects of massive social networks. we study the algorithmic and structural properties of very large, realistic social contact networks. we consider the social network for the city of portland, oregon, usa, developed as a part of the transims/episims project at the los alamos national laboratory. the most expressive social contact network is a bipartite graph, with two types of nodes: people and locations; edges represent people visiting locations on a typical day. three types of results are presented. (i) our empirical results show that many basic characteristics of the dataset are well-modeled by a random graph approach suggested by fan chung graham and lincoln lu (the cl-model), with a power-law degree distribution. (ii) we obtain fast approximation algorithms for computing basic structural properties such as clustering coefficients and shortest paths distribution. we also study the dominating set problem for such networks; this problem arose in connection with optimal sensor-placement for disease-detection. we present a fast approximation algorithm for computing near-optimal dominating sets. (iii) given the close approximations provided by the cl-model to our original dataset and the large data-volume, we investigate fast methods for generating such random graphs. we present methods that can generate such a random network in near-linear time, and show that these variants asymptotically share many key features of the cl-model, and also match the portland social network.the structural results have been used to study the impact of policy decisions for controlling large-scale epidemics in urban environments.
restructuring ordered binary trees. we consider the problem of restructuring an ordered binary tree t, preserving the in-order sequence of its nodes, so as to reduce its height to some target value h. such a restructuring necessarily involves the downward displacement of some of the nodes of t. our results, focusing both on the maximum displacement over all nodes and on the maximum displacement over leaves only, provide (i) an explicit tradeoff between the worst-case displacement and the height restriction (including a family of trees that exhibit the worst-case displacements) and (ii) efficient algorithms to achieve height-restricted restructuring while minimizing the maximum node displacement.
optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. we establish tight bounds on the intrinsic cost (either minimizing delay d for fixed server and receiver bandwidths, or minimizing server bandwidth for fixed delay and receiver bandwidth) of broadcasting a movie of length m over a channel of bandwidth s in such a way that a receiver (with bandwidth r), starting at an arbitrary time t, can download the movie so that it can begin playback after a delay of at most d time units.our bounds are realized by a simple abstract protocol that partitions the movie into a fixed number of segments, partitions the server bandwidth into an equivalent number of equal bandwidth subchannels, and broadcasts each segment repeatedly on its flown subchannel. this protocol can be implemented as a concrete discrete protocol in which movie information is packaged into discrete fixed length packets using only a modest overhead (measured in terms of increased delay or server bandwidth).our primary contribution is a lower bound on the required delay that applies in a very general model of communication. this lower bound matches the behaviour of our abstract protocol in the limit as the number of segments approaches infinity. we are also able to relate its behaviour to arbitrary protocols that have a fixed number of segments.