waashk/dblp huggingface dataset:
the bin-covering technique for thresholding random geometric graph properties. we study the emerging phenomenon of ad hoc, sensor-based communication networks. the communication is modeled by the geometric random graph model g(n, r, &ell;) where n points randomly placed within [0, &ell;]d form the nodes, and any two nodes that correspond to points at most distance r away from each other are connected. we study fundamental properties of g(n, r, &ell;) of interest: connectivity, coverage, and routing-stretch. our main contribution is a simple analysis technique we call bin-covering that we apply uniformly to get first known, (asymptotically) tight thresholds for each of these properties. typically, in the past, geometric random graph analyses involved sophisticated methods from continuum percolation theory; on contrast, our bin-covering approach is discrete and very simple, yet it gives us tight threshold bounds. the technique also yields algorithmic benefits as illustrated by a simple local routing algorithm for finding paths with low stretch. our specific results should also prove interesting to the networking community that has seen a recent increase in the study of geometric random graphs motivated by engineering ad hoc networks.
efficient bundle sorting. many data sets to be sorted consist of a limited number of distinct keys. sorting such data sets can be thought of as bundling together identical keys and having the bundles placed in order; we therefore denote this as bundle sorting. we describe an efficient algorithm for bundle sorting in external memory, which requires at most c(n/b) logm/bk disk accesses, where n is the number of keys, m is the size of internal memory, k is the number of distinct keys, b is the transfer block size, and 2 < c < 4. for moderately sized k, this bound circumvents the theta((n/b) logm/b (n/b)) i/o lower bound known for general sorting. we show that our algorithm is optimal by proving a matching lower bound for bundle sorting. the improved running time of bundle sorting over general sorting can be significant in practice, as demonstrated by experimentation. an important feature of the new algorithm is that it is executed "in-place," requiring no additional disk space.
rangesum histograms. a rangesum query to an array a is a pair (l, r) of range endpoints, which should be answered by &sigma;l&le;ira[i]. to compress a, we consider representing an array a lossily by a histogram, a function that is constant on each of a small number of buckets. we then answer range queries from h instead of from a, i.e., as &sigma;l&le;irh[i]. an optimal rangesum histogram h for this purpose is one whose bucket boundaries and constant heights within buckets are chosen to minimize the expected square error, el, r[(&sigma;l&le;ira[i]--&sigma;l&le;irh[i].)2], assuming each rangesum query is equally likely. rangesum histograms find many applications in database systems.in a degenerate variation, all rangesum queries are over ranges of size one, namely, individual points; histograms optimal for this special case are called pointwise optimal histograms. pointwise optimal histogram is a classical notion in statistics and approximation theory, but rangesum optimal histogram appears to be novel in these areas. while optimal pointwise histograms can be constructed efficiently by simple dynamic progrmming, no efficient (even approximate) general rangesmn histogram construction algorithms were previously known. in practice, all commercial database systems use heuristically built histograms for pointwise and rangesum queries.we present the first general algorithms for approximate rangesum histograms. given parameter b, we denote by (&alpha;, &beta;)-approximation an algorithm to produce a (&alpha;b)-bucket histogram with error at most &beta; times the error of the optimal b-bucket histogram. we give a (2, 1)-approximation with runtime o(n2b), a (2, 1+∊)-approximation with runtime n + (b log(n)/∊)o(1) (1), and a (1, 1 + ∊)-approximation with runtime o(b3n4/∊2). we also consider the problem of dynamic maintenance of rangesum histograms for data updated by additive changes, and we give a (2, 1 + ∊)-approximation that uses space (blog(n)/∊)o(1) and time (blog(n)/∊)o(1) for update and query operations. the bounds are nearly competitive with some of the best known bounds for constructing pointwise optimal histograms modulo small additional number of buckets used; however, rangesum histograms are substantially harder to construct because of the long range dependence between subproblems.
efficient oblivious transfer protocols. 1 introduction oblivious transfer (ot) protocols allow one party, the sender, to transmit part of its inputs to another party, the chooser, in a manner that protects both of them: the sender is assured that the chooser does not receive more information than it is entitled, while the chooser is assured that the sender does not learn which part of the inputs it received. ot is used as a key component in many applications of cryptography. its computational requirements are quite demanding and they are likely to be the bottleneck in many applications that invoke it. 1.1 contributions. this paper presents several significant improvements to oblivious transfer (ot) protocols of strings, and in particular: (i) improving the efficiency of applications which many invocations of oblivious transfer. (ii) providing the first two-round ot protocol whose security analysis does not invoke the random oracle model.
the directed circular arrangement problem. we consider the problem of embedding a directed graph onto evenly-spaced points on a circle while minimizing the total weighted edge length. we present the first poly-logarithmic approximation factor algorithm for this problem which yields an approximation factor of o(log n log log n), thus improving the previous &otilde;(&radic;n) approximation factor. in order to achieve this, we introduce a new problem which we call the directed penalized linear arrangement. this problem generalizes both the directed feedback edge set problem and the directed linear arrangement problem. we present an o(log n log log n) approximation factor algorithm for this newly defined problem. our solution uses two distinct directed metrics ("right" and "left") which together yield a lower bound on the value of an optimal solution. in addition, we define a sequence of new directed spreading metrics that are used for applying the algorithm recursively on smaller subgraphs. the new spreading metrics allow us to define an asymmetric region growing procedure that accounts simultaneously for both incoming and outgoing edges. to the best of our knowledge, this is the first time that a region growing procedure is defined in directed graphs that allows for such an accounting.
a certifying algorithm for the consecutive-ones property. we give a forbidden substructure characterization of set families that have the consecutive-ones property, and a linear time algorithm to find the forbidden substructure if a set family does not have the property. the forbidden substructure has size o(n), where n is the size of the domain. the pq tree is a well-known data structure for representing all consecutive-ones orderings. we show that it is given by a substitution decomposition of arbitrary set families that has not been described previously. this observation gives a generalization of the pq tree to arbitrary set families, and we give a linear-time algorithm to compute it.
construction of probe interval models. an interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each pair of intersecting intervals. a probe interval graph is obtained from an interval graph by designating a subset p of vertices as probes, and removing the edges between pairs of vertices in the remaining set n of non-probes. we examine the problem of finding and representing possible layouts of the intervals, given a probe interval graph. we obtain an o(n + m log n) bound, where n is the number of vertices and m is the number of edges. the problem is motivated by an application to molecular biology.
randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees. the strong link between matroids and matching is used to extend the ideas that resulted in the design of random nc algorithms for matching to obtain rnc algorithms for the well-known problems of finding an arboresence and a maximum cardinality set of edge-disjoint spanning trees in a graph. the key tools used are linear algebra and randomization.
a new algorithm for protein folding in the hp model. we consider the problem of protein folding in the hp model on the two-dimensional square lattice. this problem is combinatorially equivalent to folding a string of 0's and 1's so that the string forms a self-avoiding walk on the lattice and the number of adjacent pairs of 1's is maximized. we present a linear-time 1/3-approximation algorithm for this problem, improving on the previous best approximation factor of 1/4. the approximation guarantee of this algorithm is based on an upper bound presented by hart and istrail [6] and used in all previous papers that address this problem. we show that this upper bound cannot be used to obtain an approximation factor better than 1/2.
multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs. chung and ross (siam j. comput., 20, 1991) conjectured that the minimum number m(n, r) of middle-state switches for the symmetric 3-stage clos network c(n, m(n, r), r) to be rearrangeable in the multirate enviroment is at most 2n -- 1. this problem is equivalent to a generalized version of the biparite graph edge coloring problem. the best bounds known so far on the function m(n, r) is 11n/9 &le; m(n, r) &le; 41n/16 + o(1), for n, r &ge; 2, derived by du-gao-hwang-kim (siam j. comput., 28, 1999). in this paper, we make several contributions. firstly, we give evidence to show that even a stronger result might hold. in particular, we give a coloring algorithm to show that m(n, r) &le; [(r + 1)n/2], which implies m(n, 2) &le; [3n/2] - stronger than the conjectured value of 2n -- 1. secondly, we derive that m(2, r) = 3 by an elegant argument. lastly, we improve both the best upper and lower bounds given above: [5n/4] &le; m(n, r) &le; 2n -- 1 + [(r -- 1)/2], where the upper bound is an improvement over 41n/16 when r is relatively small compared to n. we also conjecture that m(n, r) &le; [2n (1 -- 1/2(r)].
analyzing and characterizing small-world graphs. we study variants of kleinberg's small-world model where we start with a k-dimensional grid and add a random directed edge from each node. the probability u's random edge is to v is proportional to d(u,v)-r where d(u,v) is the lattice distance and r is a parameter of the model.for a k-dimensional grid, we show that these graphs have poly-log expected diameter when k < r < 2k, but have polynomial expected diameter when r > 2k. this shows an interesting phase-transition between small-world and "large-world" graphs.we also present a general framework to construct classes of small-world graphs with &theta;(log n) expected diameter, which includes several existing settings such as kleinberg's grid-based and tree-based settings [15].we also generalize the idea of 'adding links with probability &alpha; the inverse distance' to design small-world graphs. we use semi-metric and metric functions to abstract distance to create a class of random graphs where almost all pairs of nodes are connected by a path of length o (log n), and using only local information we can find paths of poly-log length.
srpt optimally utilizes faster machines to minimize flow time. we analyze the shortest remaining processing time (srpt) algorithm with respect to the problem of scheduling n jobs with release times on m identical machines to minimize total flow time. it is known that srpt is optimal if m = 1 but that srpt has a worstcase approximation ratio of &theta;(min(log n/m, log &delta;)) for this problem, where &delta; is the ratio of the length of the longest job divided by the length of the shortest job. it has previously been shown that srpt is able to use faster machines to produce a schedule as good as an optimal algorithm using slower machines. we now show that srpt optimally uses these faster machines with respect to the worst-case approximation ratio. that is, if srpt is given machines that are s &ge; 2 - 1/m times as fast as those used by an optimal algorithm, srpt's flow time is at least s times smaller than the flow time incurred by the optimal algorithm. clearly no algorithm can offer a better worst-case guarantee, and we show that existing algorithms with similar performance guarantees to srpt without resource augmentation do not optimally use extra resources.
hole and antihole detection in graphs. in this paper, we study the problems of detecting holes and antiholes in general undirected graphs and present algorithms for them, which, for a graph on n vertices and m edges, run in o(n + m2) time and require o(nm) space; we thus provide a solution to the open problem posed by hayward, spinrad, and sritharan in [12] asking for an o(n4)-time algorithm for finding holes in arbitrary graphs. the key element of the algorithms is a special type of depth-first search traversal which proceeds along p4s (i.e., chordless paths on four vertices) of the input graph. we also describe a different approach which allows us to detect antiholes in graphs that do not contain chordless cycles on 5 vertices in o(n + m2) time requiring o(n + m) space. our algorithms are simple and can be easily used in practice. additionally, we show how our detection algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph; the augmentation takes o(n + m) time and space.
strong concentration for quicksort. let qn be the random number of comparisons made by quicksort in sorting n distinct keys, when we assume that all n! possible orderings are equally likely. known results concerning moments for qn do not show how rare it is for qn to make large deviations from its mean. here we give a good approximation to the probability of such a large deviation, and find that this probability is quite small. as well as the basic quicksort we consider the variant in which the partitioning key is chosen as the median of (2t+1) keys.
approximating connectivity augmentation problems. let g &equals; (v,e) be an undirected graph and let s &sube; v. the s-connectivity &lambda;sg(u,v) of a node pair (u,v) in g is the maximum number of uv-paths that no two of them have an edge or a node in s &minus; {u,v} in common. the corresponding connectivity augmentation (ca) problem is: given a graph g &equals; (v,e), a node subset s &sube; v, and a nonnegative integer requirement function r(u,v) on v &times; v, add a minimum size set f of new edges to g so that &lambda;sg+f(u,v) &ge; r(u,v) for all (u,v) &isin; v &times; v. three extensively studied particular cases are: the edge-ca (s &equals; &empty;), the node-ca (s &equals; v), and the element-ca (r(u,v)&equals; 0 whenever u &isin; s or v &isin; s). a polynomial-time algorithm for edge-ca was developed by frank. in this article we consider the element-ca and the node-ca, that are np-hard even for r(u,v) &isin; {0,2}. the best known ratios for these problems were: 2 for element-ca and o(rmax &sdot; ln n) for node-ca, where rmax &equals; maxu,v &isin; v r(u,v) and n &equals; &verbar;v&verbar;. our main result is a 7/4-approximation algorithm for the element-ca, improving the previously best known 2-approximation. for element-ca with r(u,v) &isin; {0,1,2} we give a 3/2-approximation algorithm. these approximation ratios are based on a new splitting-off theorem, which implies an improved lower bound on the number of edges needed to cover a skew-supermodular set function. for node-ca we establish the following approximation threshold: node-ca with r(u,v) &isin; {0,k} cannot be approximated within o(2log1&minus;&epsis; n) for any fixed &epsis; > 0, unless np &sube; dtime(npolylog(n)).
dag-width: connectivity measure for directed graphs. tree-width is a very useful connectivity measure for undirected graphs. we propose a new definition, called dag-width, for directed graphs which measures how close a graph is to a directed acyclic graph. in addition we define a cops-and-robber game and show that this game characterises exactly the class of graphs of bounded dag-width. a comparison of dag-width with tree-width and directed tree-width follows. finally we show that np-complete problems can be solved in polynomial time on graphs of bounded dag-width.
triangulating vertex colored graphs. this paper examines the class of vertex-colored graphs that can be triangulated without the introduction of edges between vertices of the same color. this is related to a fundamental and long-standing problem for numerical taxonomists, called the perfect phylogeny problem. these problems are known to be polynomially equivalent and np-complete. this paper presents a dynamic programming algorithm that can be used to determine whether a given vertex-colored graph can be so triangulated and that runs in $o((n+m(k-2))^{k+1})$ time, where the graph has $n$ vertices, $m$ edges, and $k$ colors. the corresponding algorithm for the perfect phylogeny problem runs in $o(r^{k+1} k^{k+1} + sk^2 )$ time, where $s$ species are defined by $k$ $r$-state characters.
tail estimates for the space complexity of randomized incremental algorithms. we give tail estimates for the space complexity of randomized incremental algorithms for line segment intersection in the plane. for n the number of segments, m is the number of intersections, and m &ge; n ln n ln(3) n, there is a constant c such that the probability that the total space cost exceeds c times the expected space cost is e-&ohgr;(m/(n ln n)).
approximate local search in combinatorial optimization. local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal solutions for np-hard optimization problems. we introduce the concept of ε-local optimality and show that an ε-local optimum can be identified in time polynomial in the problem size and 1=ε whenever the corresponding neighborhood can be searched in polynomial time, for ε > 0. if the neighborhood can be searched in polynomial time for a &delta;-local optimum, a variation of our main algorithm produces a (&delta; + ε)-local optimum in time polynomial in the problem size and 1/ε. as a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better solution---the so-called augmentation problem---has a fully polynomial-time approximation scheme.
certifying large branch-width. branch-width is defined for graphs, matroids, and, more generally, arbitrary symmetric submodular functions. for a finite set v, a function f on the set of subsets 2v of v is submodular if f(x) + f(y) &ge; f(x &cap; y) + f(x &cup; y), and symmetric if f(x) = f(v \ x). we discuss the computational complexity of recognizing that symmetric submodular functions have branch-width at most k for fixed k. an integer-valued symmetric submodular function f on 2v is a connectivity function if f(&theta;) = 0 and f({v}) &le; 1 for all v &isin; v. we show that for each constant k, if a connectivity function f on 2v is presented by an oracle and the branch-width of f is larger than k, then there is a certificate of polynomial size (in |v|) such that a polynomial-time algorithm can verify the claim that branch-width of f is larger than k. in particular it is in conp to recognize matroids represented over a fixed field with branch-width at most k for fixed k.
metric cotype. we introduce the notion of metric cotype, a property of metric spaces related to a property of normed spaces, called rademacher cotype. apart from settling a long standing open problem in metric geometry, this property is used to prove the following dichotomy: a family of metric spaces f is either almost universal (i.e., contains any finite metric space with any distortion > 1), or there exists &alpha; > 0, and arbitrarily large n-point metrics whose distortion when embedded in any member of f is at least &omega;((log n)&alpha;). the same property is also used to prove strong non-embeddability theorems of lq into lp, when q > max{2, p}. finally we use metric cotype to obtain a new type of isoperimetric inequality on the discrete torus.
tight bounds for the partial-sums problem. we close the gaps between known lower and upper bounds for the online partial-sums problem in the ram and group models of computation. if elements are chosen from an abstract group, we prove an &omega;(lg n) lower bound on the number of algebraic operations that must be performed, matching a well-known upper bound. in the ram model with b-bit memory registers, we consider the well-studied case when the elements of the array can be changed additively by &delta;-bit integers. we give a ram algorithm that achieves a running time of &theta;(1 + lg n / lg(b / &delta;)) and prove a matching lower bound in the cell-probe model. our lower bound is for the amortized complexity, and makes minimal assumptions about the relations between n, b, and &delta;. the best previous lower bound was &omega;(lg n = (lg lg n+lg b)), and the best previous upper bound matched only in the special case b = &theta;(lg n) and &delta; = o(lg lg n).
meldable ram priority queues and minimum directed spanning trees. we consider the implementation of meldable priority queues with integer keys in the ram model. we present two new general techniques for transforming non-meldable priority queues into meldable ones. these transformations can be described symbolically as:non-meldable priority queue +union-find &larr; meldable priority queuenon-meldable priority queue +slow meldable priority queue &larr;faster meldable priority queueusing the first transformation to combine a recent non-meldable ram priority queue of thorup with the classical union-find data structure we obtain a meldable ram priority queue with an amortized cost of o(log log n&middot;&alpha;(n)) per operation, where &alpha;(n) = &alpha;(n, n) is the inverse ackermann function. using instead a randomized priority queue of han and thorup we obtain an expected amortized cost of o(&radic;(log log n) &middot; &alpha;(n)) per operation. the second transformation yields slower meldable priority queues, but the obtained queues can support the insert, find-min and decrease-key operations in constant time. in particular, by combining a randomized "atomic-heap" of thorup with, e.g., the classical fibonacci heaps of fredman and tarjan, we obtain, for every fixed ε > 0, a meldable priority queue with an expected amortized cost of o(1) for each insert, find-min and decrease-key operation, and an expected amortized cost of o((log n)1/2+ε) for each delete or meld operation.using the meldable priority queues of the first type, we obtain improved algorithms for finding minimum directed spanning trees in graphs with integer edge weights: a deterministic o(m &middot; log log n &middot; &alpha;(n)) time algorithm and a randomized o(m &middot; &radic;(log log n) &middot; &alpha;(n)) expected time algorithm. these bounds improve, for very sparse graphs, on the o(m + n log n) running time of an algorithm by gabow, galil, spencer and tarjan that works for arbitrary edge weights.