waashk/dblp huggingface dataset:
simultaneous diagonal flips in plane triangulations. simultaneous diagonal flips in plane triangulations are investigated. it is proved that every triangulation with n&thinsp;&ge;&thinsp;6 vertices has a simultaneous flip into a 4-connected triangulation, and that the set of edges to be flipped can be computed in $\cal o$(n) time. it follows that every triangulation has a simultaneous flip into a hamiltonian triangulation. this result is used to prove that for any two n-vertex triangulations, there exists a sequence of $\cal o$(logn) simultaneous flips to transform one into the other. moreover, &ohm;(log n) simultaneous flips are needed for some pairs of triangulations. the total number of edges flipped in this sequence is $\cal o$(n). the maximum size of a simultaneous flip is then studied. it is proved that every triangulation has a simultaneous flip of at least ${{1}\over{3}}({n}-{2})$ edges. on the other hand, every simultaneous flip has at most n - 2 edges, and there exist triangulations with a maximum simultaneous flip of ${{6}\over{7}}({n}-{2})$ edges. &copy; 2006 wiley periodicals, inc. j graph theory 54: 307&ndash;330, 2007 a preliminary version of this paper was published in the proceedings of the 17th annual acm-siam symposium on discrete algorithms (soda'06). research partially completed at carleton university and mcgill university (montr&eacute;al).
improved results for route planning in stochastic transportation. in the bus network problem, the goal is to generate a plan for getting from point x to point y within a city using buses in the smallest expected time. because bus arrival times are not determined by a fixed schedule but instead may be random, the problem requires more than standard shortest path techniques. in recent work, datar and ranade provide algorithms in the case where bus arrivals are assumed to be independent and exponentially distributed. we offer solutions to two important generalizations of the problem, answering open questions posed by datar and ranade. first, we provide a polynomial time algorithm for a much wider class of arrival distributions, namely those with increasing failure rate. this class includes not only exponential distributions but also uniform, normal, and gamma distributions. second, in the case where bus arrival times are independent and geometric discrete random variables, we provide an algorithm for transportation networks of buses and trains, where trains run according to a fixed schedule.
the relative worst order ratio applied to paging. the relative worst-order ratio, a relatively new measure for the quality of on-line algorithms, is extended and applied to the paging problem. we obtain results significantly different from those obtained with the competitive ratio. first, we devise a new deterministic paging algorithm, retrospective-lru, and show that, according to the relative worst-order ratio and in contrast with the competitive ratio, it performs better than lru. our experimental results, though not conclusive, are slightly positive and leave it possible that retrospective-lru or similar algorithms may be worth considering in practice. furthermore, the relative worst-order ratio (and practice) indicates that lru is better than the marking algorithm fwf, though all deterministic marking algorithms have the same competitive ratio. look-ahead is also shown to be a significant advantage with this new measure, whereas the competitive ratio does not reflect that look-ahead can be helpful. finally, with the relative worst-order ratio, as with the competitive ratio, no deterministic marking algorithm can be significantly better than lru, but the randomized algorithm mark is better than lru.
on-line restricted caching. we study the on-line caching problem in a restricted cache where each memory item can be placed in only a restricted subset of cache locations. examples of restricted caches in practice include victim caches, assist caches, and skew caches. to the best of our knowledge, all previous on-line caching studies have considered on-line caching in identical or fully-associative caches where every memory item can be placed in any cache location. in this paper, we focus on companion caches, a simple restricted cache that includes victim caches and assist caches as special cases. our results show that restricted caches are significantly more complex than identical caches. for example, we show that the commonly studied least recently used (lru) algorithm is not competitive unless cache reorganization is allowed while the performance of the first in first out (fifo) algorithm is competitive but not optimal. we then present two near optimal algorithms for this problem as well as some lower bound arguments.
single-minded unlimited supply pricing on sparse instances. we deal with the problem of finding profit-maximizing prices for a finite number of distinct goods, assuming that of each good an unlimited number of copies is available, or that goods can be reproduced at no cost (e.g., digital goods). consumers specify subsets of the goods and the maximum prices they are willing to pay. in the considered single-minded case every consumer is interested in precisely one such subset. if the goods are the edges of a graph and consumers are requesting to purchase paths in this graph, then we can think of the problem as pricing computer network connections or transportation links.we start by showing weak np-hardness of the very restricted case in which the requested subsets are nested, i.e., contained inside each other or non-intersecting, thereby resolving the previously open question whether the problem remains np-hard when the underlying graph is simply a line. using a reduction inspired by this result we present an approximation preserving reduction that proves apx-hardness even for very sparse instances defined on general graphs, where the number of requests per edge is bounded by a constant b and no path is longer than some constant l. on the algorithmic side we first present an o(log l + log b)-approximation algorithm that (almost) matches the previously best known approximation guarantee in the general case, but is especially well suited for sparse problem instances. using a new upper bounding technique we then give an o(l2)-approximation, which is the first algorithm for the general problem with an approximation ratio that does not depend on b.
competitive analysis of organization networks or multicast acknowledgement: how much to wait? we study, from the competitive analysis perspective, the trade off between communication cost and delay cost (or simply the send-or-wait dilemma) on a hierarchy (rooted tree). the problem is an abstraction of the message aggregation problem on communication networks and the organizational problem in network hierarchies. we consider the most natural variant of the problem, the distributed asynchronous regime, and give tight (within an additive constant) upper and lower bounds of the competitive ratio.we also consider the centralized version of the problem, where we combine the natural rent-to-buy strategy with prediction techniques to achieve the first constant competitive ratio algorithm for any non-trivial class of network topologies.
lower bounds for external memory dictionaries. we study trade-offs between the update time and the query time for comparison based external memory dictionaries. the main contributions of this paper are two lower bound trade offs between the i/o complexity of member queries and insertions: if n < m insertions perform at most &delta; &middot; n/b i/os, then (1) there exists a query requiring n/(m. &middot;~o(&delta;)) i/os, and (2) there exists a query requiring &omega;(log&delta;log2n ~ i/os when &delta; is o(b/log3 n) and n is at least m2. for both lower bound we describe data structures which give matching upper bounds for a wide range of parameters, thereby showing the lower bounds to be tight within these ranges.
cache-oblivious string dictionaries. we present static cache-oblivious dictionary structures for strings which provide analogues of tries and suffix trees in the cache-oblivious model. our construction takes as input either a set of strings to store, a single string for which all suffixes are to be stored, a trie, a compressed trie, or a suffix tree, and creates a cache-oblivious data structure which performs prefix queries in o(logbn + |p|/b) i/os, where n is the number of leaves in the trie, p is the query string, and b is the block size. this query cost is optimal for unbounded alphabets. the data structure uses linear space.
cache oblivious search trees via binary trees of small height. we propose a version of cache oblivious search trees which is simpler than the previous proposal of bender, demaine and farach-colton and has the same complexity bounds. in particular, our data structure avoids the use of weight balanced b-trees, and can be implemented as just a single array of data elements, without the use of pointers. the structure also improves space utilization.for storing n elements, our proposal uses (1 + &epsilon;)n times the element size of memory, and performs searches in worst case o(logb n) memory transfers, updates in amortized o((log2 n)/(&epsilon;b)) memory transfers, and range queries in worst case o(logb n + k/b) memory transfers, where k is the size of the output.the basic idea of our data structure is to maintain a dynamic binary tree of height log n+o(1) using existing methods, embed this tree in a static binary tree, which in turn is embedded in an array in a cache oblivious fashion, using the van emde boas layout of prokop.we also investigate the practicality of cache obliviousness in the area of search trees, by providing an empirical comparison of different methods for laying out a search tree in memory.
optimal construction of edge-disjoint paths in random graphs. given a graph g=(v,e) with n vertices, m edges, and a family of $\kappa$ pairs of vertices in $v$, we are interested in finding for each pair (ai, bi) a path connecting ai to bi such that the set of $\kappa$ paths so found is edge disjoint. (for arbitrary graphs the problem is ${\cal np}$-complete, although it is in ${\cal p}$ if $\kappa$ is fixed.)we present a polynomial time randomized algorithm for finding the optimal number of edge disjoint paths (up to constant factors) in the random graph gn,m for all edge densities above the connectivity threshold. (the graph is chosen first; then an adversary chooses the pairs of endpoints.) our results give the first tight bounds for the edge-disjoint paths problem for any nontrivial class of graphs.
multidimensional balanced allocations. we consider a multidimensional variant of the balls-and-bins problem, where balls correspond to random d-dimensional 0-1 vectors. this variant is motivated by a problem in load balancing documents for distributed search engines. we demonstrate the utility of the power of two choices in this domain.
worst case constant time priority queue. we present a new data structure of size 3m + &ogr;(m) bits for solving the &ldquo;discrete priority queue&rdquo; problem. when this data structure is used in combination with a new memory topology it provides an o(1) worst case time solution. in doing so we demonstrate how an unconventional, but practically implementable, memory architecture can be employed to sidestep a lower bound (of lg lg m) and achieve constant time performance.
improving table compression with combinatorial optimization. we study the problem of compressing massive tables within the partition-training paradigm introduced by buchsbaum et al. [2000], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is compressed separately by a standard, on-line compressor like gzip. we provide a new theory that unifies previous experimental observations on partitioning and heuristic observations on column permutation, all of which are used to improve compression rates. based on this theory, we devise the first on-line training algorithms for table compression, which can be applied to individual files, not just continuously operating sources; and also a new, off-line training algorithm, based on a link to the asymmetric traveling salesman problem, which improves on prior work by rearranging columns prior to partitioning. we demonstrate these results experimentally. on various test files, the on-line algorithms provide 35--55&percnt; improvement over gzip with negligible slowdown; the off-line reordering provides up to 20&percnt; further improvement over partitioning alone. we also show that a variation of the table compression problem is max-snp hard.
a data structure for arc insertion and regular path finding. if $g$ is a directed graph with labeled edges and $l$ is a fixed regular language, the {\em regular path problem}, given two nodes, $u$ and $v$, in $g$, is to find a path between $u$ and $v$ such that the labels on the arcs along that path form a string which is a member of $l$. we consider a dynamic version of this problem, adding arcs to and performing regular path queries on $g$ over $l$, and present a data structure that solves both problems in average time per operation linear in the number of nodes of the graph for any fixed regular language.
quantum property testing. a language $l$ has a property tester if there exists a probabilistic algorithm that given an input $x$ queries only a small number of bits of $x$ and distinguishes the cases as to whether $x$ is in $l$ and $x$ has large hamming distance from all $y$ in $l$. we define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. we also show there exist languages which require a large number of queries even for quantumly testing.
relating singular values and discrepancy of weighted directed graphs. various parameters have been discovered which give a measurement of the "randomness" of a graph. we consider two such parameters for directed graphs: the singular values of the (normalized) adjacency matrix and discrepancy (a measurement of how randomly edges have been placed). we will show that these two are equivalent by bounding one by the other so that if one is small then both are small. we will also give a related result for discrepancy of walks when the indegree and out-degree at each vertex is equal. both of these results follow from a more general discrepancy property of nonnegative matrices which we will state and prove.
many distances in planar graphs. let g be a planar graph with n vertices and non-negative edge-lengths. given a set of k pairs of vertices, we are interested in computing the distance in g between those k pairs of vertices. we describe how this can be achieved in o(n2/3k2/3 log n + n4/3log1/3 n) time, improving previous results for a large range of k. as possible applications, we show how this result speeds up previous algorithms for finding shortest non-contractible cycles for graphs on a bounded-genus surface or for computing the dilation of a geometric planar graph.
improved range-summable random variable construction algorithms. range-summable universal hash functions, also known as range-summable random variables, are binary-valued hash functions which can efficiently hash single values as well as ranges of values from the domain. they have found several applications in the area of data stream processing where they are used to construct sketches---small-space summaries of the input sequence.we present two new constructions of range-summable universal hash functions on n-bit strings, one based on reed-muller codes which gives k-universal hashing using o(nlog k) space and time for point operations and o(n2 log k) for range operations, and another based on a new subcode of the second-order reed-muller code, which gives 5-universal hashing using o(n) space, o(n log3 n) time for point operations, and o(n3) time for range operations.we also present a new sketch data structure using the new hash functions which improves several previous results.
approximation algorithms for the 0-extension problem. in the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semi-metric on the set of terminals. our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. this problem generalizes the multiway cut problem of dahlhaus, johnson, papadimitriou, seymour, and yannakakis and is closely related to the metric labeling problem introduced by kleinberg and tardos. we present approximation algorithms for o-extension. in arbitrary graphs, we present an &ogr;(log k)-approximation algorithm, k being the number of terminals. we also give &ogr;(1)-approximation guarantees for weighted planar graphs. our results are based on a natural metric relaxation of the problem, previously considered by karzanov. it is similar in flavor to the linear programming relaxation of garg, vazirani, and yannakakis for the multicut problem and similar to relaxations for other graph partitioning problems. we prove that the integrality ratio of the metric relaxation is at least c&radic;lgk for a positive c for infinitely many k. our results improve some of the results of kleinberg and tardos and they further our understanding on how to use metric relaxations.
the list partition problem for graphs. we consider the problem of partitioning the vertex-set of a graph into at most k parts a1, a2,..., ak, where it may be specified that ai induce a stable set, a clique, or an arbitrary subgraph, and pairs ai, aj (i &ne; j) be completely non-adjacent, completely adjacent, or arbitrarily adjacent. this problem is generalized to the list version which specifies for each vertex a list of parts in which the vertex is allowed to be placed. many well-known graph problems can be formulated as list partition problems: e.g. 3-colourability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. we classify, with the exception of two polynomially equivalent problems, each list partition problem with k = 4 as either solvable in polynomial time or np-complete. in doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. this also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or np-complete.
the complexity of heaps. in this paper, we investigate the complexity of heaps. in particular, we study the construction problem and the search problem for heaps. we derive an adversary-based lower bound for the heap construction problem. it is shown that 1.5(n + 1)&ndash;log(n + 1)&ndash;2 comparisons are necessary to construct a heap of size n in the worst case. this is the first non-trivial adversary lower bound for this problem, which improves the previous best lower bound based on an information theoretical argument for the heap construction. furthermore, we prove fairly trivial tight upper and lower bounds on the number of comparisons needed to search for a given element in a heap. an optimal 3/4n-time search algorithm is presented. our lower bound for searching is also demonstrated by an adversary argument, which improves the information theory bound for the problem as well.
computing contour trees in all dimensions. we show that contour trees can be computed in all dimensions by a simple algorithm that merges two trees. our algorithm extends, simplifies, and improves work of tarasov and vyalyi and of van kreveld et al.
hill-climbing finds random planted bisections. we analyze the behavior of hill-climbing algorithms for the minimum bisection problem on instances drawn from the &ldquo;planted bisection&rdquo; random graph model, gn,p,q, previously studied in [3, 4, 10, 11, 14, 9, 7]. this is one of the few problem distributions for which various popular heuristic methods, such as simulated annealing, have been proven to succeed. however, it has been open whether these sophisticated methods were necessary, or whether simpler heuristics would also work. juels [14] made the first progress towards an answer by showing that simple hill-climbing does suffice for very wide separations between p and q. here we give a more complete answer. a simple, polynomial-time, hill-climbing algorithm for this problem is given and shown to succeed in finding the planted bisection with high probability if p - q = &ohgr; (n-&frac12;ln3n). for dense graphs, this matches the condition for optimality of the planted bisection to within a polylogarithmic factor. furthermore, we show that a generic randomized hill-climbing algorithm succeeds in finding the planted bisection in polynomial time if p - q = &ohgr; (n-&frac14; ln3 n), for any &isin; > 0. this algorithm, studied also by [14], is a degenerate case of both metropolis and go-with-the-winners, and the range here properly includes those analyzed in [11, 9, 14]. so this result implies, extends, and unifies those from [11, 9, 14]. thus, to get a provable distinction between simulated annealing and hill-climbing for natural problems will require considerable progress both on new positive results for sa and new negative results for hill-climbing methods.
an o(ve) algorithm for ear decompositions of matching-covered graphs. our main result is an o(nm)-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, improving on the previous best running time of o(nm2). where n and m denote the number of nodes and edges. the improvement in the running time comes from new structural results that give a sharpened version of lov&aacute;sz and plummer's two-ear theorem. our algorithm is based on o(nm)-time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. (to the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.)
the influence of search engines on preferential attachment. there is much current interest in the evolution of social networks, especially, the web graph, through time. "preferential attachment" and the "copying model" are well-known models which explain the observed degree distribution of the web graph reasonably closely. we claim that the presence of highly popular search engines like google substantially mediate the act of hyperlink creation by limiting the author's attention to a small set of "celebrity" urls. page authors (who are also web surfers) frequently (with probability p) locate pages using a search engine. then they link to popular pages among those they visit. we initiate an analysis of this more realistic process, and show that the celebrity nodes eventually accumulate a constant fraction of all links created whp, and that the degrees of the other nodes still follow a power-law distribution, but with a steeper power: pr(degree = k) &alpha; k-(1+2/(1-p)) whp. our analysis adds evidence to the recent concern that search engines offer new web pages a steep, self-sustaining barrier to entry to well-connected, entrenched web communities.
a deterministic near-linear time algorithm for finding minimum cuts in planar graphs. we present a simple deterministic o(n log2 n)-time divide-and-conquer algorithm for finding minimum cuts in planar graphs. this can be compared to a randomized algorithm for general graphs by karger that runs in time o(m log3 n) and also a deterministic algorithm for general graphs by nagamochi and ibaraki that runs in time o(mn + n2 log n). we use shortest paths in the dual graphs to partition the problem, and use the relationship between minimum cuts in primal graphs and shortest paths in dual graphs to find minimum cuts that cross the partitions efficiently.