waashk/dblp huggingface dataset:
scaling and related techniques for geometry problems three techniques in computational geometry are explored: scaling solves a problem by viewing it at increasing levels of numerical precision; activation is a restricted type of update operation, useful in sweep algorithms; the cartesian tree is a data structure for problems involving maximums and minimums. these techniques solve the minimum spanning tree problem in rk1 and rk@@@@ in o(n(lg n)rlg lg n) time and o(n) space, where for rk@@@@ and k &ge; 3, r &equil; k&minus;2; for rk1, r &equil; 1, 2, 4 for k &equil; 3, 4, 5 and r &equil; k for k > 5. other problems solved include rk1and rk all nearest neighbors, post office and maximum spanning tree; rk maxima, rk rectangle searching problems, and zkp all nearest neighbors (1 &le; p &le; @@@@).
algorithms for edge coloring bipartite graphs a minimum edge coloring of a bipartite graph is a partition of the edges into &dgr; matchings, where &dgr; is the maximum degree in the graph. coloring algorithms are presented that use time o(min(&brvbar;e&brvbar; &dgr; log n, &brvbar;e&brvbar; @@@@n log n, n2log &dgr;)) and space o(n&dgr;). this compares favorably to the previous o(&brvbar;e&brvbar; [equation] log &dgr;) time bound. the coloring algorithms also find maximum matchings on regular (or semi-regular) bipartite graphs. the time bounds compare favorably to the o(&brvbar;e&brvbar @@@@n) matching algorithm, expect when [equation] &le; &dgr; &le; @@@@n log n.
a linear-time algorithm for a special case of disjoint set union this paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a &ldquo;union tree&rdquo;) is known in advance. the algorithm executes an intermixed sequence of m union and find operations on n elements in 0(m+n) time and 0(n) space. this is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0(m&agr;(m+n, n)+n) time and 0(n) space, where &agr; is a functional inverse of ackermann's function. used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving a number of other problems, including two-processor scheduling, the off-line min problem, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. the algorithm obtains its efficiency by combining a fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. the algorithm extends to the case in which single-node additions to the union tree are allowed. the extended algorithm is useful in finding maximum cardinality matchings on nonbipartite graphs.
almost-optimum speed-ups of algorithms for bipartite matching and related problems we present algorithms for matching and related problems that run on an erew pram with p processors. given is a bipartite graph g with n vertices, m edges, and integral edge costs at most n in magnitude. we give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in &ogr;(&radic;nm log (nn)(log(2p))/p) time and &ogr;(m) space, for p &le; m/(&radic;nlog2n). for p = 1 this improves the best known sequential algorithm, and is within a factor of log (nn) of the best known bound for the problem without costs (maximum cardinality matching). for p > 1 the time is within a factor of log p of optimum speed-up. extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). our ideas also extend to general graph matching problems.
forests, frames and games: algorithms for matroid sums and applications this paper presents improved algorithms for matroid partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned into k forests. the notion of a clamp in a matroid sum is introduced. efficient algorithms for problems involving clumps are presented. applications of these algorithms to problems arising in the study of structural rigidity of graphs, the shannon switching game and others are given.
compatible sequences and a slow winkler percolation. two infinite 0-1 sequences are called compatible when it is possible to cast out 0's from both in such a way that they become complementary to each other. answering a question of peter winkler, we show that if the two 0-1-sequences are random i.i.d. and independent from each other, with probability p of 1's, then if p is sufficiently small they are compatible with positive probability. the question is equivalent to a certain dependent percolation with a power-law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially.
clairvoyant scheduling of random walks. two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. about 10 years ago, peter winkler asked the question: for which graphs are two independent walks compatible with positive probability. up to now, no such graphs were found. we show in this paper that large complete graphs have this property. the question is equivalent to a certain dependent percolation with a power-law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially.
reliable computation with cellular automata we construct a one-dimensional array of cellular automata on which arbitrarily large computations can be implemented reliably, even though each automaton at each step makes an error with some constant probability. to compute reliably with unreliable components, von neumann proposed boolean circuits whose intricate interconnection pattern (arising from the error-correcting organization) he had to assume to be immune to errors. in a uniform cellular medium, the error-correcting organization exists only in &ldquo;software&rdquo;, therefore errors threaten to disable it. the real technical novelty of the paper is therefore the construction of a self-repairing organization.
from a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. set agreement, where processors decisions constitute a set of outputs, is notoriously harder to analyze than consensus where the decisions are restricted to a single output. this is because the topological questions that underly set agreement are not about simple connectivity as in consensus. analyzing set agreement inspired the discovery of the relation between topology and distributed algorithms, and consequently the impossibility of asynchronous set agreement.yet, the application of topological reasoning has been to the static case, that of asynchronous and synchronous tasks. it is not known yet for example, how to characterize starvation-free solvability of non-terminating tasks. non-terminating tasks are dynamic entities with no defined end. in a similar vain, early deciding synchronous set agreement, in which the number of rounds it takes a processor to decide adapts to the actual number of failures, falls in this category of dynamic entities.this paper develops a simulation technique that brings to bear topological results to deal with the dynamic situation that arises with early decisions. the novelty of the new simulation is the ability of simulators to look back at the transcript of past rounds of the simulation to influence their current behavior.using our new technique, we not only re-derive past results, but we propose and prove a lower bound to synchronous early stopping set agreement. we then provide an algorithm to match the lower bound. our technique uses the bg simulation, in the most creative way it was used to-date, to obtain a rather simple reduction from a static asynchronous impossibility. this reduction is a simple alternative to yet unknown topological argument, and in fact may suggest the way of finding such an argument.
computing nash equilibria for scheduling on restricted parallel links. we consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. thus, the problem is equivalent to the correspondingly restricted problem of assigning n jobs to m parallel machines. in a pure nash equilibrium, no user may improve its own individual cost (delay) by unilaterally switching to another link from its set of allowed links. as our main result, we introduce a polynomial time algorithm to compute from any given assignment a pure nash equilibrium with non-increased makespan. the algorithm gradually changes a given assignment by pushing unsplittable user traffics through a network that is defined by the users and the links. here, we use ideas from blocking flows. furthermore, we use similar techniques as in the generic preflow-push algorithm to approximate a schedule with minimum makespan, gaining an improved approximation factor of 2 - 1/w1 for identical links, where w1 is the largest user traffic. we extend this result to related links, gaining an approximation factor of 2. our approximation algorithms run in polynomial time. we close with tight upper bounds on the coordination ratio for pure nash equilibria.
lower bounds on the amount of randomness in private computation. we consider the amount of randomness necessary in information-theoretic private protocols. we prove that at least ω(log n) random bits are necessary for the t-private computation of the function xor by n players, for any t ≥ 2. in view of the upper bound of o(t2log(n/t))[19], this bound is tight, up to constant factors, for any fixed t. for a class of protocols obeying certain restrictions, we give stronger lower bounds of ω(t log (n/t)). we note that all known randomness efficient private protocols designed specifically for xor belong to this class. all our lower bounds hold for the "trusted dealer" model as well, and the ω(t log (n/t)) lower bound for restricted protocols is tight, up to constant factors, for any t ≥ 2 in this model.in comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 ≤ t = o(log n). our results also show that already for t = 2, ω(log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players.our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. these properties in turn imply that the number of random bits used by the players is large.
a theorem on sensitivity and applications in private computation. in this paper we prove a theorem that gives an (almost) tight upper bound on the sensitivity of a multiple-output boolean function in terms of the sensitivity of its coordinates and the size of the range of the function. we apply this theorem to get improved lower bounds on the time (number of rounds) to compute boolean functions by private protocols. these bounds are given in terms of the sensitivity of the function being computed and the amount of randomness used by the private protocol. these lower bounds are tight (up to constant factors) for the case of the xor function and together with the results in [e. kushilevitz and a. rosén, siam j. discrete math., 11 (1998), pp. 61--80.] establish a tight (up to constant factors) tradeoff between randomness and time in private computation.
on the validity and complexity of bounded resolution several procedures based on (not necessarily regular) resolution for checking whether a formula in cn3 is contradictory are considered. the procedures use various methods of bounding the size of the clauses which are generated. the following results are obtained: 1) all of the proposed procedures which are forced to run in polynomial time do not always work&mdash;i.e., they do not identify all contradictory formulas. 2) those which always work must run in exponential time. the exponential lower bounds for these procedures do not follow from tseitin's lower bound for regular resolution since these procedures also allow nonregular resolution trees.
real-time algorithms for string-matching and palindrome recognition we give a sufficient condition when an on-line algorithm can be transformed into a real-time algorithm. we use this condition to construct real-time algorithms for string-matching and palindrome recognition problems by random access machines and by turing machines.
optimal parallel algorithms for string matching let wram [pram] be a parallel computer with p processors (ram's) which share a common memory and are allowed simultaneous reads and writes [only simultaneous reads]. the only type of simultaneous writes allowed is a simultaneous and: several processors may write o simultaneously into the same memory cell. let t be the time bound of the computer. we design below families of parallel algorithms that solve the string matching problem with inputs of size n (n is the sum of lengths of the pattern and the text) and have the following performance in terms of p, t and n: 1. for wram: pt &equil; o(n) for for p &le; n/log n. 2. for pram: pt &equil; o(n) for p &le; n/log2n. 3. for wram: t &equil; constant for p &equil; nl+&egr; and any &egr; > o. 4. for wram: t &equil; o(log n/log log n) for p &equil; n. similar families are also obtained for the problem of finding all initial palindromes of a given string.
a constant-time optimal parallel string-matching algorithm given a pattern string, we describe a way to preprocess it. we design a constant-time optimal parallel algorithm for finding all occurences of the (preprocessed) pattern in any given text.
network flow and generalized path compression an o(evlog2v) algorithm for finding the maximal flow in networks is described. it is asymptotically better than the other known algorithms if e &equil; o(v2&minus;&egr;) for some &egr;>0. the analysis of the running time exploits the discovery of a phenomenon similar to (but more general than) path compression, although the union find algorithm is not used. the time bound is shown to be tight in terms of v and e by exhibiting a family of networks that require &ohgr;(evlog2v) time.++
an efficient general purpose parallel computer in this paper we investigate the question of what is a good way to interconnect a large number of processors. our main result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.
well-separated pair decomposition for the unit-disk graph metric and its applications. we extend the classic notion of well-separated pair decomposition [p. b. callahan and s. r. kosaraju, j. acm, 42 (1975), pp. 67--90] to the unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. we show that for the unit-disk graph metric of n points in the plane and for any constant $c\geq 1$, there exists a c-well-separated pair decomposition with o(n log n) pairs, and the decomposition can be computed in o(n log n) time. we also show that for the unit-ball graph metric in k dimensions where $k\geq 3$, there exists a c-well-separated pair decomposition with o(n2-2/k) pairs, and the bound is tight in the worst case. we present the application of the well-separated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.
some np-complete geometric problems we show that the steiner tree problem and traveling salesman problem for points in the plane are np-complete when distances are measured either by the rectilinear (manhattan) metric or by a natural discretized version of the euclidean metric. our proofs also indicate that the problems are np-hard if the distance measure is the (unmodified) euclidean metric. however, for reasons we discuss, there is some question as to whether these problems, or even the well-solved minimum spanning tree problem, are in np when the distance measure is the euclidean metric.
worst-case analysis of memory allocation algorithms various memory allocation problems can be modeled by the following abstract problem. given a list a &equil; (&agr;1,&agr;2,...&agr;n,) of real numbers in the range (0, 1], place these in a minimum number of &ldquo;bins&rdquo; so that no bin holds numbers summing to more than 1. we let a* be the smallest number of bins into which the numbers of list a may be placed. since a general placement algorithm for attaining a* appears to be impractical, it is important to determine good heuristic methods for assigning numbers of bins. we consider four such simple methods and analyze the worst-case performance of each, closely bounding the maximum of the ratio of the number of bins used by each method applied to list a to the optimal quantity a*.
some simplified np-complete problems it is widely believed that showing a problem to be np-complete is tantamount to proving its computational intractability. in this paper we show that a number of np-complete problems remain np-complete even when their domains are substantially restricted. first we show the completeness of simple max cut (max cut with edge weights restricted to value 1), and, as a corollary, the completeness of the optimal linear arrangement problem. we then show that even if the domains of the node cover and directed hamiltonian path problems are restricted to planar graphs, the two problems remain np-complete, and that these and other graph problems remain np-complete even when their domains are restricted to graphs with low node degrees. for graph 3-colorability, node cover, and undirected hamiltonian circuit, we determine essentially the lowest possible upper bounds on node degree for which the problems remain np-complete.
saving an epsilon: a 2-approximation for the k-mst problem in graphs. we present a polynomial time 2-approximation algorithm for the problem of finding the minimum tree that spans at least k vertices. our result also leads to a 2-approximation algorithm for finding the minimum tour that visits k vertices and to a 3-approximation algorithm for the problem of finding the maximum number of vertices that can be spanned by a tree of length at most a given bound.
auction algorithms for market equilibrium. in this paper we study algorithms for computing market equilibrium in markets with linear utility functions. the buyers in the market have an initial endowment given by a portfolio of goods. the market equilibrium problem is to compute a price vector that ensures market clearing, i.e., the demand of a positively priced good equals its supply, and given the prices, each buyer maximizes its utility. the problem is of considerable interest in economics. this paper presents a formulation of the market equilibrium problem as a parameterized linear program. we construct a family of duals corrresponding to these parameterized linear programs and show that finding the market equilibrium is the same as finding a linear program from this family of linear programs. the market-clearing conditions arise naturally from complementary slackness conditions. we then define an auction mechanism that computes prices such that approximate market clearing is achieved. the algorithm we obtain outperforms previously known methods.
minimizing average flow time on related machines. we give the first on-line poly-logarithmic competitve algorithm for minimizing average flow time with preemption on related machines, i.e., when machines can have different speeds. this also yields the first poly-logarithmic polynomial time approximation algorithm for this problem.more specifically, we give an o(log2 p • log s)-competitive algorithm, where p is the ratio of the biggest and the smallest processing time of a job, and s is the ratio of the highest and the smallest speed of a machine. our algorithm also has the nice property that it is non-migratory. the scheduling algorithm is based on the concept of making jobs wait for a long enough time before scheduling them on slow machines.
approximate max-flow min-(multi)cut theorems and their applications. consider the multicommodity flow problem in which the object is to maximize the sum of commodities routed. we prove the following approximate max-flow min-multicut theorem: $$ \dst \frac{\mbox{\rm min multicut}}{o(\log k)} \leq \mbox{ \rm max flow } \leq \mbox{ \rm min multicut}, $$ \noindent where $k$ is the number of commodities. our proof is constructive; it enables us to find a multicut within $o(\log k)$ of the max flow (and hence also the optimal multicut). in addition, the proof technique provides a unified framework in which one can also analyse the case of flows with specified demands of leighton and rao and klein et al. and thereby obtain an improved bound for the latter problem.
on the equivalence of schemes one objective of the study of schemes for computation is that of finding general methods for checking or verifying a given program against its specifications. if one views the program and its specification as presenting two supposedly equivalent schemes for a computation, then the objective reduces to one of finding general methods for determining whether, in fact, the two schemes are equivalent. unfortunately, for many classes of schemes which are sufficiently powerful, this &ldquo;equivalence problem&rdquo; is not decidable, i.e. there are no general methods capable of determining, in all cases, whether two schemes in the class are equivalent. in this report we investigate the question of which classes of schemes have decidable equivalence problems, or, in otherwords the question of for which classes of schemes there exist general methods capable of determining equivalence.
parallel algorithms for algebraic problems in borodin-von zur gathen-hopcroft[82] the following program is laid out: obtain a &ldquo;theory package for parallel algebraic computations&rdquo;, i.e. fast parallel computations for the widely used problems of symbolic manipulation in an algebraic context. in that paper, two basic problems were considered: solving systems of linear equations and computing the gcd of two polynomials, both over arbitrary ground fields. the present paper continues this program, and fast parallel solutions to the following algebraic problems are given: computing all entries of the extended euclidean scheme of two polynomials over an arbitrary field, gcd and lcm of many polynomials, factoring polynomials over finite fields, and the squarefree decomposition of polynomials over fields of characteristic zero and over finite fields.