waashk/dblp huggingface dataset:
scheduling split intervals. we consider the problem of scheduling jobs that are given as groups of non-intersecting segments on the real line. each job jj is associated with an interval, ij, which consists of up to t segments, for some t &ge; 1, a positive weight, wj, and two jobs are in conflict if any of their segments intersect. such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g. bandwidth in linear processor arrays), and in computational biology/geometry. the objective is to schedule a subset of non-conflicting jobs of maximum total weight.in a single machine environment, our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of t = 1 is an ordinary interval graph). we show that, for t &ge; 2, this problem is apx-hard, even for highly restricted instances. our main result is a 2t-approximation algorithm for general instances, based on a novel fractional version of the local ratio technique. previously, the problem was considered only for proper union graphs, a restricted subclass of t-interval graphs, and the approximation factor achieved was (2t - 1 + 1/2t). a bi-criteria polynomial time approximation scheme (ptas) is developed for the subclass of t-union graphs.in the online case, we consider uniform weight jobs that consist of at most two segments. we show that when the resulting 2-interval graph is proper, a simple greedy algorithm is 3-competitive, while any randomized algorithm has competitive ratio at least 2.5. for general instances, we give a randomized o(log2 r)-competitive (or o((log r)2+&epsilon;)-competitive) algorithm, where r is the known (unknown) ratio between the longest and the shortest segment in the input sequence.
incentive-compatible online auctions for digital goods. goldberg et al. [6] recently began the study of incentive-compatible auctions for digital goods, that is, goods which are available in unlimited supply. many digital goods, however, such as books, music, and software, are sold continuously, rather than in a single round, as is the case for traditional auctions. hence, it is important to consider what happens in the online version of such auctions. we define a model for online auctions for digital goods, and within this model, we examine auctions in which bidders have an incentive to bid their true valuations, that is, incentive-compatible auctions. since the best offline auctions achieve revenue comparable to the revenue of the optimal fixed pricing scheme, we use the latter as our benchmark. we show that deterministic auctions perform poorly relative to this benchmark, but we give a randomized auction which is within a factor o(exp&radic;log log h) of the benchmark, where h is the ratio between the highest and lowest bids. as part of this result, we also give a new offline auction, which improves upon the previously best auction in a certain class of auctions for digital goods. we also give lower bounds for both randomized and deterministic online auctions for digital goods.
reductions in streaming algorithms, with an application to counting triangles in graphs. we introduce reductions in the streaming model as a tool in the design of streaming algorithms. we develop the concept of list-efficient streaming algorithms that are essential to the design of efficient streaming algorithms through reductions.our results include a suite of list-efficient streaming algorithms for basic statistical primitives. using the reduction paradigm along with these tools, we design streaming algorithms for approximately counting the number of triangles in a graph presented as a stream.a specific highlight of our work is the first algorithm for the number of distinct elements in a data stream that achieves arbitrary approximation factors. (independently, trevisan [tre01] has solved this problem via a different approach; our algorithm has the advantage of being list-efficient.)
on the discrete bak-sneppen model of self-organized criticality. we propose a discrete variant of the bak-sneppen model for self-organized criticality. in this process, a configuration is an n-bit word, and at each step one chooses a random bit of minimum value (usually a zero) and replaces it and its two neighbors by independent bernoulli variables with parameter p. we prove bounds on the average number of ones in the stationary distribution and present experimental results.
adaptive intersection and t-threshold problems. consider the problem of computing the intersection of k sorted sets. in the comparison model, we prove a new lower bound which depends on the non-deterministic complexity of the instance, and implies that the algorithm of demaine, l&oacute;pez-ortiz and munro [2] is usually optimal in this "adaptive" sense. we extend the lower bound and the algorithm to the t-threshold problem, which consists in finding the elements which are in at least t of the k sets. these problems are motivated by boolean queries in text database systems.
a lower bound for hellbronn's triangle problem in dimensions. in this paper we show a lower bound for the generalization of heilbronn's triangle problem to d dimensions; namely, we show that there exists a set s of n points in the d-dimensional unit cube so that every d+1 points of s define a simplex of volume $\omega (\frac{1}{n^d})$. we also show a constructive incremental positioning of n points in a unit 3-cube for which every tetrahedron defined by four of these points has volume $\omega (\frac{1}{n^4})$.
straight-skeleton based contour interpolation. in this paper we present an efficient method for interpolating a piecewise-linear surface between two parallel slices, each consisting of an arbitrary number of (possibly nested) polygons that define 'material' and 'nonmaterial' regions. this problem has applications to medical imaging, geographic information systems, etc. our method is fully automatic and is guaranteed to produce non-self-intersecting surfaces in all cases regardless of the number of contours in each slice, their complexity and geometry, and the depth of their hierarchy of nesting. the method is based on computing cells in the overlay of the slices, that form the symmetric difference between them. then, the straight skeletons of the selected cells guide the triangulation of these cells. finally, the resulting triangles are lifted up in space to form an interpolating surface. we provide some experimental results on various complex examples to show the good and robust performance of our algorithm.
dynamic construction of bluetooth scatternets of fixed degree and low diameter. bluetooth is a promising recent radio technology for ad hoc networking. bluetooth networks are based on connecting together piconets, to form a scatternet. the structure of the scatternet, and the way the scatternet is built and maintained, are not part of the bluetooth specifications, but have a tremendous impact on the performance of the network. we present an efficient distributed algorithm for bluetooth scatternet construction. the resulting scatternet is scalable and our construction is dynamic in the sense that nodes can join and leave the network at their convenience. for fixed constant degree of nodes, the resulting diameter is polylogarithmic in the size of the network, and the connectivity of the masters is high. we also give a routing protocol adapted to the specific scatternet topology returned by our algorithm. this protocol does not require complicated path-discovery methods, but is based on a simple virtual labeling of the devices participating in the scatternet.
on page migration and other related task systems. this paper is concerned with the page migration (or file migration) problem (black and sleator, technical report cmu-cs-89-201, department of computer science, carnegie-mellon university, 1989) as part of a large class of on-line problems. the page migration problem deals with the management of pages residing in a network of processors. in the classical problem there is only one copy of each page which is accessed by different processors over time. the page is allowed to be migrated between processors. however a migration incurs higher communication cost than an access (proportionally to the page size). the problem is that of deciding when and where to migrate the page in order to lower access costs. a more general setting is the k-page migration problem where we wish to maintain k copies of the page. the page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. we deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (borodin et al., j. acm 39(4) (1992) 745-763). given a c-competitive algorithm for a task system we show how to obtain a deterministic o(c2) and randomized o(c) competitive algorithms for the corresponding relaxed task system. the result implies deterministic algorithms for k-page migration by using k-server (manasse et al., j. algorithms 11(2) (1990) 208-230) algorithms, and for network leasing by using generalized steiner tree algorithms (awerbuch et al., proc 7th ann. acm-siam symp. on discrete algorithms, january 1996, pp. 68-74), as well as providing solutions for natural generalizations of other problems (e.g. storage rearrangement (fiat et al., proc. 36th ann. ieee symp. on foundations of computer science, october 1995, pp. 392-403)). we further study some special cases of the k-page migration problem and get optimal deterministic algorithms. for the classical page migration problem we present a deterministic algorithm that achieves a competitive ratio of ~ 4:086, improving upon the previously best competitive ratio of 7 (awerbuch et al., proc. 25th acm symp. on theory of computing, may 1993, pp. 164-173). (the current lower bound on the problem is ~ 3:148 (chrobak et al., j. algorithms 24(1) (1997) 124-157). copyright 2001 elsevier science b.v.
multiprocessor scheduling with rejection. we consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. an instance of the problem is given by $m$ identical parallel machines and a set of $n$ jobs, with each job characterized by a processing time and a penalty. in the on-line version the jobs become available one by one and we have to schedule or reject a job before we have any information about future jobs. the objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs.the main result is a $1+\phi\approx 2.618$ competitive algorithm for the on-line version of the problem, where $\phi$ is the golden ratio. a matching lower bound shows that this is the best possible algorithm working for all $m$. for fixed $m$ we give improved bounds; in particular, for $m=2$ we give a $\phi\approx 1.618$ competitive algorithm, which is best possible.for the off-line problem we present a fully polynomial approximation scheme for fixed $m$ and a polynomial approximation scheme for arbitrary $m$. moreover, we present an approximation algorithm which runs in time $o(n\log n)$ for arbitrary $m$ and guarantees a $2-\frac{1}{m}$ approximation ratio.
multi-embedding and path approximation of metric spaces. metric embeddings have become a frequent tool in the design of algorithms. the applicability is often dependent on how high the embedding's distortion is. for example embedding into ultrametrics (or arbitrary trees) requires linear distortion. using probabilistic metric embeddings, the bound reduces to o(log nlog logn). yet, the lower bound is still logarithmic.we make a step further in the direction of bypassing this difficulty. we define "multi-embeddings" of metric spaces where a point is mapped onto a set of points, while keeping the target metric being of polynomial size and preserving the distortion of paths. the distortion obtained with such multi-embeddings into ultrametrics is at most o(log &delta; log log &delta;) where &delta; is the (normalized) diameter, and probabilistically o(log n log log log n). in particular, for expander graphs, we are able to obtain constant distortions embeddings into trees vs. the &omega;(logn) lower bound for all previous notions of embeddings.we demonstrate the algorithmic application of the new embeddings by obtaining improvements for two well-known problems: group steiner tree and metrical task systems.
dimension reduction for ultrametrics. we prove that an ultrametric on n points can be embedded in ldp with distortion at most 1 + ε, and d = o(ε-2 log n). this bound matches the best known bound for the special case of an equilateral space.
randomized -server algorithms for growth-rate bounded graphs. the k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. while the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k) competitive ratios. this goal may be approached by using probabilistic metric approximation techniques. this paper gives the first results in this direction obtaining o(k) competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k. prior to this work no result of this type was known beyond results for specific metric spaces.
kinetic collision detection between two simple polygons. we design a kinetic data structure for detecting collisions between two simple polygons in motion. in order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. we show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting.
maintaining all-pairs approximate shortest paths under deletion of edges. we present a hierarchical scheme for efficiently maintaining all-pairs approximate shortest paths in undirected unweighted graphs under deletions of edges.an &alpha;-approximate shortest-path between two vertices is a path of length at-most &alpha; times the length of the shortest path. for maintaining &alpha;-approximate shortest paths for all pairs of vertices separated by distance &le; d in a graph of n vertices, we present the first o(nd) update time algorithm based on our hierarchical scheme. in particular, the update time per edge deletion achieved by our algorithm is &otilde;(min{&radic;nd,(nd)2/3}) for 3-approximate shortest-paths, and &otilde;(min{&radic;nd,(nd)4/7}) for 7-approximate shortest-paths. for graphs with &theta;(n2) edges, we achieve even further improvement in update time : &otilde;(&radic;nd) for 3-approximate shortest-paths, and &otilde;(3&radic;nd2) for 5-approximate shortest-paths.for maintaining all-pairs approximate shortest-paths, weimprove the previous &otilde;(n3/2)bound on the update time per edge deletion for approximation factor &ge; 3. in particular, update time achieved by our algorithm is &otilde;(n10/9) for 3-approximate shortest-paths, &otilde;(n14/13) for 5-approximate shortest-paths, and &otilde;(n28/27) for 7-approximate shortest-paths.all our algorithms achieve optimal query time and are simple to implement.
new constructions of (alpha, beta)-spanners and purely additive spanners. an (&alpha;, &beta;)-spanner of an unweighted graph g is a subgraph h that approximates distances in g in the following sense. for any two vertices u, v: &delta;h (u, v) &le; &alpha;&delta;g(u, v) + &beta;, where &delta;g is the distance w.r.t. g. it is well known that there exist (multiplicative) (2k - 1, 0)-spanners of size o(n1+1/k) and that there exist (purely additive) (1, 2)-spanners of size o(n3/2). however no other (1, o(1))-spanners are known to exist.in this paper we develop a couple new techniques for constructing (&alpha;, &beta;)-spanners. the first result is a purely additive (1, 6)-spanner of size o(n4/3). our construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well-approximated by paths already purchased. this general approach should lead to new spanner constructions.the second result is a truly simple linear time construction of (k, k - 1)-spanners with size o(n1+1/k). in a distributed network the algorithm terminates in a constant number of rounds and has expected size o(n1+1/k). the new idea here is primarily in the analysis of the construction. we show that a few simple and local rules for picking spanner edges induce seemingly coordinated global behavior.
approximate distance oracles for unweighted graphs in õ(n) time. let g(v, e) be an undirected weighted graph with |v| = n, |e| = m. recently thorup and zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly in o(n2) space, and yet answers any approximate distance query in constant time. they named this data-structure approximate distance oracle because of this feature. given an integer k < 1, a (2k-1)-approximate distance oracle requires o(kn1+1/k) space and answers a (2k-1)-approximate distance query in o(k) time. thorup and zwick showed that a (2k - 1)-approximate distance oracle can be computed in o(kmn1/k) time, and posed the following question : can (2k - 1)-approximate distance oracle be computed in &otilde;(n2) time?in this paper, we answer their question in affirmative for unweighted graphs. we present an algorithm that computes (2k -1)-approximate distance oracle for a given unweighted graph in &otilde;(n2) time. one of the new ideas used in the improved algorithm also leads to the first linear time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph.
oblivious string embeddings and edit distance approximations. we introduce an oblivious embedding that maps strings of length n under edit distance to strings of length at most n/r under edit distance for any value of parameter r. for any given r, our embedding provides a distortion of &otilde;(r1+&mu;) for some &mu; = o(1), which we prove to be (almost) optimal. the embedding can be computed in &otilde;(21/&mu;n) time.we also show how to use the main ideas behind the construction of our embedding to obtain an efficient algorithm for approximating the edit distance between two strings. more specifically, for any 1 > &epsilon; &ge; 0, we describe an algorithm to compute the edit distance d(s, r) between two strings s and r of length n in time &otilde;(n1+&epsilon;), within an approximation factor of min{n1-&epsilon;/3+o(1), (d(s, r/n&epsilon;)1/2+o(1)}. for the case of &epsilon; = 0, we get a &otilde;(n)-time algorithm that approximates the edit distance within a factor of min{n1/3+o(1), d(s, r)1/2+o(1)}, improving the recent result of bar-yossef et al. [2].
reconstructing strings from random traces. we are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. our goal is to exactly reconstruct the string t from these observed traces. we initiate here a study of deletion rates for which we can successfully reconstruct the original string using a small number of samples. we investigate a simple reconstruction algorithm called bitwise majority alignment that uses majority voting (with suitable shifts) to determine each bit of the original string. we show that for random strings t, we can reconstruct the original string (w.h.p.) for q = o(1/ log n) using only o(log n) samples. for arbitrary strings t, we show that a simple modification of bitwise majority alignment reconstructs a string that has identical structure to the original string (w.h.p.) for q = o(1/n1/2+ε) using o(1) samples. in this case, using o(n log n) samples, we can reconstruct the original string exactly. our setting can be viewed as the study of an idealized biological evolutionary process where the only possible mutations are random deletions. our goal is to understand at what mutation rates, a small number of observed samples can be correctly aligned to reconstruct the parent string.in the process of establishing these results, we show that bitwise majority alignment has an interesting self-correcting property whereby local distortions in the traces do not generate errors in the reconstruction and eventually get corrected.
dynamic point location in general subdivisions. the dynamic planar point location problem is the task of maintaining a dynamic set s of n non-intersecting, except possibly at endpoints, line segments in the plane under the following operations: &bull;locate(q point): report the segment immediately above q, i.e., the first segment intersected by an upward vertical ray starting at q; &bull;insert(s segment): add segment s to the collection s segments; &bull;delete(s segment): remove segment s from the collection s of segments. we present a solution which requires space o(n), has query and insertion time o(log n loglog n) and deletion time o(log2 n). a query time below o(log2 n) was previously only known for monotone subdivisions and horizontal segments and required non-linear space.
sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. in the multicommodity rent-or-buy (mrob) network design problems, we are given a network together with a set of k terminal pairs (s1, t1), &hellip;, (sk, tk. the goal is to provision the network so that a given amount of flow can be shipped between si and ti for all 1 &le; i &le; k simultaneously. in order to provision the network, one can either rent capacity on edges at some cost per unit of flow, or buy them at some larger fixed cost. bought edges have no incremental, flow-dependent cost. the overall objective is to minimize the total provisioning cost. recently, gupta et al. [2003a] presented a 12-approximation for the mrob problem. their algroithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate steiner forest for these pairs. this technique had previously been introduced [gupta et al. 2003b] for the single-sink rent-or-buy network design problem. in this article we give a 6.828-approximation for the mrob problem by refining the algorithm of gupta et al. and simplifying their analysis. the improvement in our article is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the steiner forest problem due to agrawal et al. [1995]. our result significantly reduces the gap between the single-sink and multisink case.
efficient proper 2-coloring of almost disjoint hypergraphs. let a be an n-uniform hypergraph. assume that the maximum degree of a is d = d(a) (local condition), and |a| = n = n(a) (global condition). by the lov&aacute;sz local lemma (l.l.l.), if d < 2n/8n, then a has a proper 2-coloring (i.e. there is no monochromatic edge) independently of the value of n (n can be infinite). unfortunately l.l.l. is a pure existence argument which does not give any clue of how to find a proper 2-coloring. a hypergraph with the property that any two edges have at most one point in common is called almost disjoint (e.g. a family of lines). assume that a is an n-uniform almost disjoint hypergraph. in this special case, we provide a polynomial time (in terms of n) algorithm to find a proper 2-coloring under the slightly weaker condition that d < (2 - &delta;)n and n is less than a doubly exponential function of n.