waashk/dblp huggingface dataset:
the bloomier filter: an efficient data structure for static support lookup tables. we introduce the bloomier filter, a data structure for compactly encoding a function with static support in order to support approximate evaluation queries. our construction generalizes the classical bloom filter, an ingenious hashing scheme heavily used in networks and databases, whose main attribute---space efficiency---is achieved at the expense of a tiny false-positive rate. whereas bloom filters can handle only set membership queries, our bloomier filters can deal with arbitrary functions. we give several designs varying in simplicity and optimality, and we provide lower bounds to prove the (near) optimality of our constructions.
embedding k-outerplanar graphs into l1. we show that the shortest-path metric of any $k$-outerplanar graph, for any fixed $k$, can be approximated by a probability distribution over tree metrics with constant distortion and hence also embedded into $\ell_1$ with constant distortion. these graphs play a central role in polynomial time approximation schemes for many np-hard optimization problems on general planar graphs and include the family of weighted $k\times n$ planar grids. this result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for $k$-outerplanar graphs, thus extending a theorem of okamura and seymour [j. combin. theory ser. b, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of gupta et al. [combinatorica, 24 (2004), pp. 233-269] for treewidth-2 graphs. in addition, we obtain improved approximation ratios for $k$-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. we conjecture that these embeddings for $k$-outerplanar graphs may serve as building blocks for $\ell_1$ embeddings of more general metrics.
edge disjoint paths revisited. the approximability of the maximum edge disjoint paths problem (edp) in directed graphs was seemingly settled by the &omega;(m1/2-&epsilon;)-hardness result of guruswami et al. [10] and the o(&radic;m) approximation achievable via both the natural lp relaxation [19] and the greedy algorithm [11, 12]. here m is the number of edges in the graph. however, we observe that the hardness of approximation shown in [10] applies to sparse graphs and hence when expressed as a function of n, the number of vertices, only an &omega;(n1/2-&epsilon;)-hardness follows. on the other hand, the o(&radic;m)-approximation algorithms do not guarantee a sub-linear (in terms of n) approximation algorithm for dense graphs. we note that a similar gap exists in the known results on the integrality gap of the natural lp relaxation: an &omega;(&radic;n) lower bound and an o(&radic;m) upper bound. motivated by this discrepancy in the upper and lower bounds we study algorithms for the edp in directed and undirected graphs obtaining improved approximation ratios. we show that the greedy algorithm has an approximation ratio of o(min(n2/3, &radic;m)) in undirected graphs and a ratio of o(min(n4/5, &radic;m)) in directed graphs. for ayclic graphs we give an o(&radic;n log n) approximation via lp rounding. these are the first sub-linear approximation ratios for edp. our results also extend to edp with weights and to the unsplittable flow problem with uniform edge capacities.
approximation algorithms for the metric labeling problem via a new linear programming formulation. we consider approximation algorithms for the metric labeling problem. this problem was introduced in a recent paper by kleinberg and tardos [20], and captures many classification problems that arise in computer vision and related fields. they gave an &ogr;(log k log log k) approximation for the general case where k is the number of labels and a 2-approximation for the uniform metric case. more recently, gupta and tardos [15] gave a 4-approximation for the truncated linear metric, a natural non-uniform metric motivated by practical applications to image restoration and visual correspondence. in this paper we introduce a natural integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. in particular, we show that the integrality gap of our lp is bounded by &ogr;(log k log log k) for general metric and 2 for the uniform metric thus matching the ratios in [20]. we also develop an algorithm based on our lp that achieves a ratio of 2 + &radic;2 &sime; 3.414 for the truncated linear metric improving the ratio given in [15]. our algorithm uses the fact that the integrality gap of our lp is 1 on a linear metric. we believe that our formulation has the potential to provide improved approximation algorithms for the general case and other useful special cases. finally, our formulation admits general non-metric distance functions. this leads to a non-trivial approximation guarantee for a non-metric case that arises in practice [21], namely the truncated quadratic distance function. we note here that there are non-metric distance functions for which no bounded approximation ratio is achievable.
approximation techniques for average completion time scheduling. we consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. recent work has led to constant-factor approximations for this problem based on solving a preemptive or linear programming relaxation and then using the solution to get an ordering on the jobs. we introduce several new techniques which generalize this basic paradigm. we use these ideas to obtain improved approximation algorithms for one-machine scheduling to minimize average completion time with release dates. in the process, we obtain an optimal randomized on-line algorithm for the same problem that beats a lower bound for deterministic on-line algorithms. we consider extensions to the case of parallel machine scheduling, and for this we introduce two new ideas: first, we show that a preemptive one-machine relaxation is a powerful tool for designing parallel machine scheduling algorithms that simultaneously produce good approximations and have small running times; second, we show that a nongreedy "rounding" of the relaxation yields better approximations than a greedy one. we also prove a general theorem relating the value of one-machine relaxations to that of the schedules obtained for the original m-machine problems. this theorem applies even when there are precedence constraints on the jobs. we apply this result to obtain improved approximation ratios for precedence graphs such as in-trees, out-trees, and series-parallel graphs.
on -median clustering in high dimensions. we study approximation algorithms for k-median clustering. we obtain small coresets for k-median clustering in metric spaces as well as in euclidean spaces. specifically, in rd, those coresets are of size with only polynomial dependency on d. this leads to a (1 + &epsilon;)-approximation algorithm for k-median clustering in rd, with running time o(ndk +2(k/&epsilon;)o(1)d2n&sigma;), for any &sigma; > 0. this is an improvement over previous results [5, 20, 21]. we also provide fast constant factor approximation algorithms for k-median clustering in finite metric spaces.we use those coresets to compute (1 + &epsilon;)-approximation k-median clustering in the streaming model of computation, using only o(k2de-2log8 n) space, where the points are taken from rd. this is the first streaming algorithm, for this problem, that has space complexity with only polynomial dependency on the dimension.
invadable self-assembly: combining robustness with efficiency. dna self-assembly is emerging as a key paradigm for nano-technology, nano-computation, and several related disciplines. in nature, dna self-assembly is often equipped with explicit mechanisms for both error prevention and error correction. for artificial self-assembly, these problems are even more important since we are interested in assembling large systems with great precision. so far, theoretical studies of dna self-assembly have primarily focused on the efficiency of the assembly process in terms of the program size and the running time. in this paper, we perform a preliminary study of algorithms for dna self-assembly that are both robust and efficient.strand invasion is an important error-correction mechanism observed in several natural self-assembling systems. we first define invadable self-assemblies as self-assembling systems which can effectively use the strand invasion mechanism for error-correction. we then show that o(log2 n/ log log n) tiles are sufficient to assemble an n &times; n square in this model. the running time of our system is &otilde; (n). we obtain our result by growing a counter which simulates chinese remaindering. the running time and the program size of our invadable system are within polylogarithmic factors of known lower bounds for general systems, i.e. the efficiency penalty for obtaining robustness is small in our model. we also show how to simulate an arbitrary turing machine using an invadable self-assembly system.
polygonal path approximation with angle constraints. we present efficient geometric algorithms for several problems of approximating an n-vertex polygonal path with angle constraints in the d-d space for any fixed d &gne; 2, improving significantly the corresponding graph- theoretic solutions based on known techniques (e.g., by (nearly) a factor of n for d = 2, 3). as a key step in our solutions, we formulate and solve an interesting problem called off-line ball exclusion search (olbes), that may be of interest on its own.
k-pair delay constrained minimum cost routing in undirected networks. we study a problem related to qos routing in an undirected network where each edge has a delay and a cost. given a k-pair routing request {(si, ti, di)&brvbar;i = l,&hellip;,k} where si is ith source node, ti is ith destination node, and di, is the ith delay tolerance, we want to compute a minimum cost network which contains an si-ti path whose delay is at most di for every i. we present an fptas for this problem when k is a constant.
constructing finite field extensions with large order elements. in this paper, we present an algorithm that, given a fixed prime power $q$ and a positive integer $n$, finds an integer $n \in [n, 2qn]$ and an element $\alpha \in \mbox{\bf f}_{q^n}$ of order greater than $ 5.8^{n / \log_q n}$, in time polynomial in $n$. we present another algorithm that finds an integer $n \in [n, n+o(n^{0.77})]$ and an element $\alpha \in \mbox{\bf f}_{q^n}$ of order at least $ 5.8^{\sqrt{n}}$, in time polynomial in $n$. our result is inspired by the recent aks primality testing algorithm [m. agrawal, n. kayal, and n. saxena, ann. of math. (2), 160 (2004), pp. 781-793] and the subsequent improvements [p. berrizbeitia, math. comp., 74 (2005), pp. 2043-2059, q. cheng, in proceedings of the 23rd annual international cryptology conference (crypto 2003), d. boneh, ed., lecture notes in comput. sci. 2729, springer-verlag, berlin, 2003, pp. 338-348, d. j. bernstein, math. comp., 76 (2007), pp. 389-403].
quality meshing with weighted delaunay refinement. delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. the only poor quality tetrahedra, called slivers, that can occur in such a mesh can be eliminated by the sliver exudation method. this method has been shown to work for periodic point sets, but not with boundaries. recently a randomized point-placement strategy has been proposed to remove slivers while conforming to a given boundary. in this paper we present a deterministic algorithm for generating a weighted delaunay mesh which respects the input boundary and has no poor quality tetrahedron including slivers. as in previous work, we assume that no input angle is acute. our result is achieved by combining the weight pumping method for sliver exudation and the delaunay refinement method for boundary conformation.
dynamic skin triangulation. this paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in r3. the triangulation adapts dynamically to changing shape, curvature, and topology of the surface.
manifold reconstruction from point samples. we present an algorithm to "reconstruct" a smooth k-dimensional manifold m embedded in an euclidean space rd from a "sufficiently dense" point sample from the manifold. the algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to m. the running time is o(n log n) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).
anisotropic surface meshing. we study the problem of triangulating a smooth closed implicit surface &sigma; endowed with a 2d metric tensor that varies over &sigma;. this is commonly known as the anisotropic surface meshing problem. we extend the 2d metric tensor naturally to 3d and employ the 3d anisotropic voronoi diagram of a set p of samples on &sigma; to triangulate &sigma;. we prove that a restricted dual, mesh p, is a valid triangulation homeomorphic to &sigma; under appropriate conditions. we also develop an algorithm for constructing p and mesh p. in addition to being homeomorphic to &sigma;, each triangle in mesh p is well-shaped when measured using the 3d metric tensors of its vertices. users can set upper bounds on the anisotropic edge lengths and the angles between the surface normals at vertices and the normals of incident triangles (measured both isotropically and anisotropically).
graded conforming delaunay tetrahedralization with bounded radius-edge ratio. we propose an algorithm to compute a conforming delaunay mesh of a polyhedral domain. arbitrarily small input angles are allowed. the output mesh is graded and has bounded radius-edge ratio everywhere.
motorcycle graphs and straight skeletons. we present a new algorithm to compute motorcycle graphs. it runs in $o(n \sqrt{n}\log n)$ time when n is the number of motorcycles. we give a new characterization of the straight skeleton of a nondegenerate polygon. for a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected $o(n\sqrt{h+1}\log^2 n)$ time. combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in $o(n\sqrt{h+1}\log^2 n+r \sqrt{r} \log r)$ expected time. in particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in $o(n\sqrt{n}\log^2n)$ expected time.
on finding a guard that sees most and a shop that sells most. we present a near-quadratic time algorithm that computes a point inside a simple polygon p having approximately the largest visibility polygon inside p, and near-linear time algorithm for finding the point that will have approximately the largest voronoi region when added to an n-point set. we apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.
center and diameter problems in plane triangulations and quadrangulations. in this note, we present first linear time algorithms for computing the center and the diameter of several classes of face regular plane graphs: triangulations with inner vertices of degree &ge; 6, quadrangulations with inner vertices of degree &ge; 4 and the subgraphs of the regular hexagonal grid bounded by a simple circuit of this grid.
buckets, heaps, lists, and monotone priority queues. we introduce the heap-on-top (hot) priority queue data structure that combines the multilevel bucket data structure of denardo and fox with a heap. our data structure has superior operation bounds than either structure taken alone. we use the new data structure to obtain an improved bound for dijkstra's shortest path algorithm. we also discuss a practical implementation of hot queues. our experimental results in the context of dijkstra's algorithm show that this implementation of hot queues performs very well and is more robust than implementations based only on heap or multilevel bucket data structures.
orderly spanning trees with applications to graph encoding and graph drawing. the canonical ordering for triconnected planar graphs is a powerful method for designing graph algorithms. this paper introduces the orderly pair of connected planar graphs, which extends the concept of canonical ordering to planar graphs not required to be triconnected. let g be a connected planar graph. we give a linear-time algorithm that obtains an orderly pair (h,t) of g, where h is a planar embedding of g, and t is an orderly spanning tree of h. as applications, we show that the technique of orderly spanning trees yields (i) the best known encoding of g with query support, and (ii) the first area-optimal 2-visibility drawing of g.
a unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. we describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map $\cal m$ with $n$ vertices and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, and shortest-path queries in $\cal m$. the space requirement is $o(n\log n)$. point-location queries take time $o(\log n)$. ray-shooting and shortest-path queries take time $o(\log^3 n)$ (plus $o(k)$ time if the $k$ edges of the shortest path are reported in addition to its length). updates consist of insertions and deletions of vertices and edges, and take $o(\log^3 n)$ time (amortized for vertex updates). this is the first polylog-time dynamic data structure for shortest-path and ray-shooting queries. it is also the first dynamic point-location data structure for connected planar maps that achieves optimal query time.
a determinant-based algorithm for counting perfect matchings in a general graph. we present a simple estimator for the number of perfect matchings in a general (non-bipartite) graph. our estimator requires o(ε-23n/2) trials to obtain a (1 &plusmn; ε)-approximation of the correct value with high probability on a graph with 2n vertices in the worst case, and only a polynomial number (o(ε-2n&omega;(n)) of trials on random graphs, where &omega;(n) is any function tending to infinity.our algorithm is based on the following idea: for any graph g, construct its associated tutte matrix t, and derive a random matrix b from it by replacing each variable in t with &plusmn;1 uniformly at random; then output det b. this estimator is a natural generalization of the godsil--gutman estimator for matchings in a bipartite graph, and our analysis of its performance on random graphs borrows generously from frieze and jerrum's analysis of a similar estimator for bipartite graphs.
approximation for minimum triangulation of convex polyhedra. the minimum triangulation of a convex polyhedron is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. since finding the minimum triangulation of convex polyhedra was recently shown to be np-hard, it becomes significant to find algorithms that give good approximation. in this paper, we give a new triangulation algorithm with an improved approximation ratio 2 - &ohgr;(1/&radic;n). we also show that this is best possible for algorithms that only consider the combinatorial structure of the polyhedra.
approximation hardness of optimization problems in intersection graphs of -dimensional boxes. the maximum independent set problem in d-box graphs, i.e., in the intersection graphs of axis-parallel rectangles in rd, is a challenge open problem. for any fixed d &ge; 2 the problem is np-hard and no approximation algorithm with ratio o(logd-1 n) is known. in some restricted cases, e.g., for d-boxes with bounded aspect ratio, a ptas exists [17]. in this paper we prove apx-hardness (and hence non-existence of a ptas, unless p = np), of the maximum independent set problem in d-box graphs for any fixed d &ge; 3. we state also first explicit lower bound 443/442 on efficient approximability in such case. additionally, we provide a generic method how to prove apx-hardness for many np-hard graph optimization problems in d-box graphs for any fixed d &ge; 3. in 2-dimensional case we give a generic approach to np-hardness results for these problems in highly restricted intersection graphs of axis-parallel unit squares (alternatively, in unit disk graphs).
which formulae shrink under random restrictions? we show that the shrinkage exponent, under random restrictions, of formulae over a finite complete basis b of boolean functions is strictly greater than 1 if and only if all the functions in b are monotone increasing or monotone decreasing in each one of their variables. as a consequence, we get non-linear lower bounds on the formula complexity of the parity function over any basis composed only of monotone increasing or decreasing functions.
delaunay triangulation programs on surface data. the delaunay triangulation of a set of points in 3d can have size &theta;(n2) in the worst case, but this is rarely if ever observed in practice. we compare three production-quality delaunay triangulation programs on some 'real-world' sets of points lying on or near 2d surfaces.
external-memory exact and approximate all-pairs shortest-paths in undirected graphs. we present several new external-memory algorithms for finding all-pairs shortest paths in a v-node. e-edge undirected graph. for all-pairs shortest paths and diameter in unweighted undirected graphs we present cache-oblivious algorithms with o(v&middot;e/b log m/b e/b) i/os, where b is the block-size and m is the size of internal memory. for weighted undirected graphs we present a cache-aware apsp algorithm that performs o(v&middot;(&radic;ve/b+e/b log e/b)) i/os. we also present efficient cache-aware algorithms that find paths between all pairs of vertices in an unweighted graph with lengths within a small additive constant of the shortest path length.all of our results improve earlier results known for these problems. for approximate apsp we provide the first nontrivial results. our diameter result uses o(v + e) extra space, and all of our other algorithms use o(v2) space.
cache-oblivious dynamic programming. we present efficient cache-oblivious algorithms for several fundamental dynamic programs. these include new algorithms with improved cache performance for longest common subsequence (lcs), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. we present a new cache-oblivious framework called the gaussian elimination paradigm (gep) for gaussian elimination without pivoting that also gives cache-oblivious algorithms for floyd-warshall all-pairs shortest paths in graphs and 'simple dp', among other problems.
the wake-up problem in multi-hop radio networks. we study the problem of waking up a collection of n processors connected by a multi-hop ad-hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. each node in the network wakes-up spontaneously, or it is activated by receiving a wake-up signal from another node. all active nodes transmit the wake-up signals according to a given protocol q. the running time of is the number of steps counted from the first spontaneous wake-up, until all nodes become activated.we provide two protocols for this problem. the first one is a deterministic protocol with running time o(n5/3log n). our protocol is based on a novel concept of a rotation-tolerant selector to which we refer as a synchronizer. the second protocol is randomized, and its expected running time is o(dlog2n), where d is the diameter of the network.subsequently we show how to employ our wake-up protocols to solve two other communication primitives: leader election and clock synchronization.