waashk/dblp huggingface dataset:
on broadcasting in heterogenous networks. in this paper we study a well known broadcasting heuristic for heterogenous networks of workstations, called fastest node first. we show that this heuristic produces an optimal solution for minimizing the sum of all completion times, and in addition produces a 1.5 approximation for the problem of minimizing the maximum completion time. we extend these results to show that the same bounds can be obtained for the multicast operation on such heterogenous networks. in addition we show that the problem of minimizing the maximum completion time is n p-hard, which settles the complexity of this open problem.
approximating the minimum equivalent diagraph. the meg (minimum equivalent graph) problem is the following: "given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." this problem is np-hard; this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. the algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. the heart of the meg problem is the minimum scss (strongly connected spanning subgraph) problem --- the meg problem restricted to strongly connected digraphs. for the minimum scss problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. the algorithm and its analysis are based on the simple idea of contracting long cycles. the analysis applies directly to $2$-\exchange, a general "local improvement" algorithm, showing that its performance guarantee is 1.75.
optimal prediction for prefetching in the worst case. response time delays caused by i/o are a major problem in many systems and database applications. prefetching and cache replacement methods are attracting renewed attention because of their success in avoiding costly i/os. prefetching can be looked upon as a type of online sequential prediction, where the predictions must be accurate as well as made in a computationally efficient way. unlike other online problems, prefetching cannot admit a competitive analysis, since the optimal offline prefetcher incurs no cost when it knows the future page requests. previous analytical work on prefetching [. vitter krishnan 1991.] [j. assoc. comput. mach., 143 (1996), pp. 771--793] consisted of modeling the user as a probabilistic markov source. in this paper, we look at the much stronger form of worst-case analysis and derive a randomized algorithm for pure prefetching. we compare our algorithm for every page request sequence with the important class of finite state prefetchers, making no assumptions as to how the sequence of page requests is generated. we prove analytically that the fault rate of our online prefetching algorithm converges almost surely for every page request sequence to the fault rate of the optimal finite state prefetcher for the sequence. this analysis model can be looked upon as a generalization of the competitive framework, in that it compares an online algorithm in a worst-case manner over all sequences with a powerful yet nonclairvoyant opponent. we simultaneously achieve the computational goal of implementing our prefetcher in optimal constant expected time per prefetched page using the optimal dynamic discrete random variate generator of [. matias matias, vitter, and ni [proc. 4th annual siam/acm symposium on discrete algorithms, austin, tx, january 1993].
minimizing migrations in fair multiprocessor scheduling of persistent tasks. suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). each machine is capable of performing one unit of work in each integral time unit and each job may be executed on at most one machine at a time. the schedule needs to specify which job is to be executed on each machine in each time window. the goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair schedule. we measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. since jobs are persistent we measure the quality of the schedule by the ratio of the number of migrations to time windows. we show a tradeoff between the drift and the number of migrations. let n = qm + r with 0 < r < m (the problem is trivial for n &le; m and for r = 0). for any d &ge; 1, we show a schedule that achieves a migration ratio of r(m - r)/(n(q(d 1) + 1)) + o(1); namely, it asymptotically requires r(m - r) job migrations every n(q(d 1) + 1) time windows. we show how to implement the schedule efficiently. we prove that our algorithm is almost optimal by proving a lower bound of r(m r)/(nqd) on the migration ratio. we also give a more complicated schedule that matches the lower bound for an infinite number of instances. our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time.
hardware-assisted computation of depth contours. given a set of points p in the plane, the location depth of a point u is the minimum number of points of p lying in a closed halfplane defined by a line through u. the set of all points in the plane having location depth at least k is called the depth contour of depth k. in this paper, we present an algorithm that makes extensive use of modern graphics architectures to compute the approximate depth contours of a set of points. the output of our algorithm presents the contours as a coloring of each point with its depth value, as opposed to computing the geometric description of the contour boundary. our algorithm performs significantly better than currently known implementations, outperforming them by at least one order of magnitude and having a strictly better asymptotic growth rate.
on distributions computable by random walks on graphs. we answer a question raised by donald e. knuth and andrew c. yao, concerning the class of polynomials on [0, 1] that can be realized as the distribution function of a random variable, whose binary expansion is the output of a finite state automaton driven by unbiased coin tosses. the polynomial distribution functions which can be obtained in this way are precisely those with rational coefficients, whose derivative has no irrational roots on [0, 1].we also show, strengthening a result of knuth and yao, that all smooth distribution functions which can be obtained by such automata are polynomials.
approximation algorithms for cycle packing problems. the cycle packing number vc(g) of a graph g is the maximum number of pairwise edge-disjoint cycles in g. computing vc(g) is an np-hard problem. we present approximation algorithms for computing vc(g) in both the undirected and directed cases. in the undirected case we analyze the modified greedy algorithm suggested in [4] and show that it has approximation ratio o(&radic;log n) where n = |v(g)|, and this is tight. this improves upon the previous o(log n) upper bound for the approximation ratio of this algorithm. in the directed case we present a &radic;n-approximation algorithm. finally, we give an o(n2/3)-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset s of vertices. our approximation ratios are the currently best known ones and, in addition, provide bounds on the integrality gap of standard lp-relaxations to these problems.
a faster deterministic maximum flow algorithm. we describe a deterministic version of a 1990 cheriyan, hagerup, and mehlhorn randomized algorithm for computing the maximum flow on a directed graph with n nodes and m edges which runs in time o(mn + n2+&egr;, for any constant &egr;. this improves upon alon's 1989 bound of o(mn + n8/3log n) [a] and gives an o(mn) deterministic algorithm for all m > n1+&egr;. thus it extends the range of m/n for which an o(mn) algorithm is known, and matches the 1988 algorithm of goldberg and tarjan [gt] for smaller values of m/n.
scalable leader election. in the leader election problem, there are n processors of which (1 - b)n are good. the problem is to design a distributed protocol to elect a good leader from the set of all processors. in this paper, we present a scalable leader election protocol. our protocol is scalable in the sense that each good processor sends and processes a number of bits which is only polylogarithmic in n. (we assume no limit on the number of messages sent by bad processors.) for b < 1/3, our protocol elects a good leader with constant probability and ensures that a 1 - o(1) fraction of the good processors know this leader.we assume a point-to-point full information model. this is similar to the full information model, but harder in the sense that in a given round, a bad processor may send different messages to different processors, rather than having to broadcast the same message to every processor.to the best of our knowledge, we present the first leader election protocol that ensures that each good processor sends and processes a sublinear number of bits. having reduced the problem of leader election to one of informing all good processors of a bit held by 1 &minus; o(1) fraction of good processors, we conjecture that the solution to this problem is not possible within polylogarithmic message bounds.our techniques can be used to provide scalable solutions to byzantine agreement and other problems.
solving random satisfiable 3cnf formulas in expected polynomial time. we present an algorithm for solving 3sat instances. several algorithms have been proved to work whp (with high probability) for various sat distributions. however, an algorithm that works whp has a drawback. indeed for typical instances it works well, however for some rare inputs it does not provide a solution at all. alternatively, one could require that the algorithm always produce a correct answer but perform well on average. expected polynomial time formalizes this notion. we prove that for some natural distribution on 3cnf formulas, called planted 3sat, our algorithm has expected polynomial (in fact, almost linear) running time. the planted 3sat distribution is the set of satisfiable 3cnf formulas generated in the following manner. first, a truth assignment is picked uniformly at random. then, each clause satisfied by it is included in the formula with probability p. extending previous work for the planted 3sat distribution, we present, for the first time for a satisfiable sat distribution, an expected polynomial time algorithm. namely, it solves all 3sat instances, and over the planted distribution (with p = d/n2, d > 0 a sufficiently large constant) it runs in expected polynomial time. our results extend to k-sat for any constant k.
on the complexity of distance-based evolutionary tree reconstruction. we give the first tight lower bounds on the complexity of reconstructing k-ary evolutionary trees from additive distance data. we also consider the problem under dna-based distance estimation assumptions, where the accuracy of distance data depends on the length of the sequence and the distance. we give the first o(n2) algorithm to reconstruct trees in this context, and prove a trade-off between the length of the dna sequences and the number of distance queries needed to reconstruct the tree. we introduce new computational models for understanding this problem, which simplify the development of algorithms. we prove lower bounds in these models which apply to the type of techniques currently in use.
the price of being near-sighted. achieving a global goal based on local information is challenging, especially in complex and large-scale networks such as the internet or even the human brain. in this paper, we provide an almost tight classification of the possible trade-off between the amount of local information and the quality of the global solution for general covering and packing problems. specifically, we give a distributed algorithm using only small messages which obtains an (&rho;&delta;)1/k-approximation for general covering and packing problems in time o(k2), where &rho; depends on the lp's coefficients. if message size is unbounded, we present a second algorithm that achieves an o(n1/k) approximation in o(k) rounds. finally, we prove that these algorithms are close to optimal by giving a lower bound on the approximability of packing problems given that each node has to base its decision on information from its k-neighborhood.
deterministic boundary recognition and topology extraction for large sensor networks. we present a new framework for the crucial challenge of self-organization of a large sensor network. the basic scenario can be described as follows: given a large swarm of immobile sensor nodes that have been scattered in a polygonal region, such as a street network. nodes have no knowledge of size or shape of the environment or the position of other nodes. moreover, they have no way of measuring coordinates, geometric distances to other nodes, or their direction. their only way of interacting with other nodes is to send or to receive messages from any node that is within communication range. the objective is to develop algorithms and protocols that allow self-organization of the swarm into large-scale structures that reflect the structure of the street network, setting the stage for global routing, tracking and guiding algorithms.our algorithms work in two stages: boundary recognition and topology extraction. all steps are strictly deterministic, yield fast distributed algorithms, and make no assumption on the distribution of nodes in the environment, other than sufficient density.
upper and lower bounds on constructing alphabetic binary trees. this paper studies the long-standing open question of whether optimal alphabetic binary trees can be constructed in $o(n \lg n)$ time. we show that a class of techniques for finding optimal alphabetic trees which includes all current methods yielding $o(n \lg n)$-time algorithms are at least as hard as sorting in whatever model of computation is used. we also give $o(n)$-time algorithms for the case where all the input weights are within a constant factor of one another and when they are exponentially separated.
how to cut a cake almost fairly. in the cake cutting problem, n &ge; 2 players want to cut a cake into n pieces so that every player gets a "fair" share of the cake by his own measure. we describe a protocol with n - 1 cuts in which each player can enforce to get a share of at least 1/(2n - 2) of the cake. moreover we show that no protocol with n - 1 cuts can guarantee a better fraction.
preprocessing an undirected planar network to enable fast approximate distance queries. we describe a method for preprocessing a weighted planar undirected graph and representing the results of the preprocessing so as to facilitate subsequent approximate distance queries. for any 0 < &epsilon; < 1/10, a representation can be constructed so that computing an &epsilon;-approximate distance from one node to another takes o(&epsilon;-1) time, principally consisting of about 15&epsilon;-1 additions. the representation requires storage of 7.2&epsilon;-1n log2 n distances. by using compressed representation of the distances, the number of bytes required is about .5n&epsilon;-1(9 + 3 log &epsilon;-1)log2 n (at the expense of a small increase in query time).
critical chromatic number and the complexity of perfect packings in graphs. let h be any non-bipartite graph. we determine asymptotically the minimum degree of a graph g which ensures that g has a perfect h-packing. more precisely, we determine the smallest number &tau; having the following property: for every positive constant &gamma; there exists an integer n0 = n0(&gamma;, h) such that every graph g whose order n &ge;n0 is divisible by |h| and whose minimum degree is at least (&tau; + &gamma;) n contains a perfect h-packing. the value of &tau; depends on the relative sizes of the colour classes in the optimal colourings of h. the proof is algorithmic, which shows that the problem of finding a maximum h-packing is polynomially solvable for graphs g whose minimum degree is at least (&tau; + &gamma;)n. on the other hand, given any positive constant &gamma;, we show that for infinitely many (non-bipartite) graphs h the corresponding decision problem becomes np-complete if one considers input graphs g of minimum degree at least (&tau; - &gamma;)n.
multiple-source shortest paths in planar graphs. given an n-node planar graph with nonnegative edge-lengths, our algorithm takes o(n log n) time to construct a data structure that supports queries of the following form in o(log n) time: given a destination node t on the boundary of the infinite face, and given a start node s anywhere, find the s-to-t distance.
end-to-end packet-scheduling in wireless ad-hoc networks. packet-scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. a distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model. the main focus of our work is the development of fully-distributed (decentralized) protocols. we present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. the packet-scheduling work by l eighton, maggs and rao (combinatorica, 1994) and a basic distributed coloring procedure, originally due to luby (j. computer and system sciences, 1993), underlie many of our algorithms. experimental work of finocchi, panconesi, and silvestri (soda 2002) showed that a natural modification of luby's algorithm leads to improved performance, and a rigorous explanation of this was left as an open question; we prove that the modified algorithm is provably better in the worst-case. finally, using simulations, we study the impact of the routing strategy and the choice of parameters on the performance of our distributed algorithm for unit disk graphs.
shape matching using edit-distance: an implementation. we report on our experience with the implementation of an algorithm for comparing shapes by computing the edit-distance between their medial axes. a shape-comparison method that is robust to various visual transformations has several applications in computer vision, including organizing and querying an image database, and object recognition. there are two components to research on this problem, mathematical formulation of the shape-comparison problem and the computational solution method. we have a clear, well-defined formulation and polynomial-time algorithms for solution. previous research has involved either ill-defined formulations or heuristic methods for solution. our starting-point for the implementation is the edit-distance algorithm of klein et al. [6]. we discuss how we altered that algorithm to handle rotation-invariance while keeping down the time and storage requirements. most important, we define costs for the edit-operations and give an algorithm for computing them. we use a database of shapes to illustrates that our approach performs intuitively in categorization and indexing tasks, and our results are better than previous approaches.
a note on the set systems used for broadcast encryption. an exclusive set system is a family of subsets of a universe with the property that every large subset may be written as the union of subsets from the family. we obtain new upper bounds on the size of such families, showing that in a universe of n elements, there is a system of 48k3 (nk)r/k in subsets with the property that every subset of the universe of size n -- r can be written as the union of k subsets in the system. such sets systems form the combinatorial foundation of many broadcast encryption schemes.
on polynomial approximation to the shortest lattice vector length. we obtain a 2&ogr;(n/&isin;) time algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of n3+&isin;.
a multiple-choice secretary algorithm with applications to online auctions. in the classical secretary problem, a set s of numbers is presented to an online algorithm in random order. at any time the algorithm may stop and choose the current element, and the goal is to maximize the probability of choosing the largest element in the set. we study a variation in which the algorithm is allowed to choose k elements, and the goal is to maximize their sum. we present an algorithm whose competitive ratio is 1-o(&radic;1/k). to our knowledge, this is the first algorithm whose competitive ratio approaches 1 as k &larr; &infin;. as an application we solve an open problem in the theory of online auction mechanisms.
anytime algorithms for multi-armed bandit problems. how should a decision-maker perform repeated choices so as to optimize the average cost or benefit of those choices in the long run? this question motivates the theory of online learning, which encompasses problems such as the well-known best-expert [13, 9] and multi-armed bandit [10, 1] problems. this paper concerns a new approach to dealing with multi-armed bandit problems in which the decision-maker's strategy set is large (exponential or possibly infinite). recent theoretical progress on the analysis of algorithms for such problems (e.g. [2, 3, 8, 11, 14]) has led to improved online algorithms for problems in areas such as online routing [2], dynamic pricing mechanisms [4, 5, 12], and analysis of reputation systems in e-commerce and peer-to-peer networks [3].
conformance testing in the presence of multiple faults. conformance testing is the problem of determining if a black-box implementation i is equivalent to a specification s, where both are modeled as finite state mealy machines. the problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. traditionally conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. this is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation [41]. however, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification.in this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. we present randomized algorithms to construct checking sequences that catch faulty implementations with at most &delta; extra states, having at least r faults (where &delta; and r are parameters to the algorithm), and pass all correct implementations. we demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. one of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. we believe that this lemma will be of independent interest in the context of verifying safety properties.