waashk/dblp huggingface dataset:
optimal random number generation from a biased coin. we study the optimal generation of random numbers using a biased coin in two cases: first, when the bias is unknown, and second, when the bias is known. in the first case, we characterize the functions that use a discrete random source of unknown distribution to simulate a target discrete random variable with a given rational distribution. we identify the functions that minimize the ratio of source inputs to target outputs. we show that these optimal functions are efficiently computable. in the second case, we prove that it is impossible to construct an optimal tree algorithm recursively, using a model based on the algebraic decision tree. our model of computation is sufficiently general to encompass virtually all previously known algorithms for this problem.
external memory bfs on undirected graphs with bounded degree. we give the first external memory algorithm for breadth-first search (bfs) which achieves &ogr;(n) i/os on arbitrary undirected graphs with n nodes and maximum node degree d. let m and b < d denote the main memory size and block size, respectively. using sort(x) = &thgr;(x&divide;b &middot; log m/b x&divide;b), our algorithm needs &ogr;(n&divide;&ggr;&middot;logdb + sort(n &middot; b&ggr;)) i/os and &ogr;(n &middot; b&ggr;) external space for an arbitrary parameter 0 < &ggr; &lne; &frac12;. the result carries over to bfs, depth-first search (dfs) and single source shortest paths (sssp) on undirected planar graphs with arbitrary node degrees.
single-source shortest-paths on arbitrary directed graphs in linear average-case time. the quest for a linear-time single-source shortest-path (sssp) algorithm on directed graphs with positive edge weights is an ongoing hot research topic. while thorup recently found an &ogr;(n + m) time ram algorithm for undirected graphs with n nodes, m edges and integer edge weights in {0,&hellip;,2w - 1} where w denotes the word length, the currently best time bound for directed sparse graphs on a ram is &ogr;(n + m &middot; log log n). in the present paper we study the average-case complexity of sssp. we give a simple algorithm for arbitrary directed graphs with random edge weights uniformly distributed in [0, 1] and show that it needs linear time &ogr;(n + m) with high probability.
optimal time-space trade-offs for non-comparison-based sorting. we study the problem of sorting n integers of w bits on a unit-cost ram with word size w, and in particular consider the time-space trade-off (product of time and space in bits) for this problem. for comparison-based algorithms, the time-space complexity is known to be &theta;(n2). a result of beame shows that the lower bound also holds for non-comparison-based algorithms, but no algorithm has met this for time below the comparison-based &omega;(nlgn) lower bound.we show that if sorting within some time bound &ttilde; is possible, then time t = o(&ttilde; + nlg* n) can be achieved with high probability using space s = o(n2/t + w), which is optimal. given a deterministic priority queue using amortized time t(n) per operation and space no(1), we provide a deterministic algorithm sorting in time t = o(n(t(n) + lg* n)) with s = o(n2/t + w). both results require that w &le; n1-&omega;(1). using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time &theta;(t) for t &ge; n(lg lg n)2, and with high probability for t &ge; nlg lg n.our results imply that recent space lower bounds for deciding element distinctness in o(nlgn) time are nearly tight.
web caching using access statistics. we consider the problem of caching web pages with the objective of minimizing latency of access. demands for web domains/pages are computed using access statistics; the frequency with which these statistics change is considerably longer than the frequency of page requests. we model caches as being constrained by total size and total number of ports: each cache can handle only a limited request rate and can store only a limited number of domains (eg. modelling bounded update traffic). when the caches have fixed locations, we present a constant factor approximation to the optimum average latency while exceeding capacity constraints by a logarithmic factor. we demonstrate improved results in the special case where no replication of pages is allowed. in the alternate model where we are allowed to place our own caches in the network for a cost, we produce a constant approximation to the weighted sum of cost and average latency. finally, we consider several other variants of the problem which might arise in practice.
can the tpri structure help us to solve the algebraic eigenproblem? we modify the customary approach to solving the algebraic eigenproblem. instead of applying the qr algorithm to a hessenberg matrix, we begin with the recent unitary similarity transform into a triangular plus rank-one matrix. then we show nonunitary transforms of this matrix at a low arithmetic cost into similar arrow-head matrices. the resulting eigenproblem can be effectively solved by the known algorithms. based on some properties of the tpri matrices, we also show that the similarity transforms into both hessenberg and tpri forms tend to decrease the geometric multiplicities of the eigenvalues, and we discuss some relevant research topics.
selfish routing with atomic players. one of the most successful applications of the price of anarchy---the worst-case ratio between the objective function values of noncooperative equilibria and optima---is to "selfish routing", a classical model of how independent network users route traffic in a congested network. however, almost all existing work on this topic (e.g., [2, 5, 7]) assumes a large population of very small network users, so that the actions of a single individual have negligible impact on the cost incurred by others. this assumption---in game theory terminology, that the game is nonatomic---is obviously not justifiable in all applications.
the mathematics of playing golf. we consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. solving instances from this class to optimality is an np-hard problem. we show that for the cases with k &le; 2, every optimal solution is integral. in strong contrast to this, for every k &ge; 3 there exist instances where every optimal solution takes non-integral values.
can entropy characterize performance of online algorithms?. we focus in this work on an aspect of online computation that is not addressed by the standard competitive analysis. namely, identifying request sequences for which non-trivial online algorithms are useful versus request sequences for which all algorithms perform equally bad. the motivation for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. to utilize these features the operating system needs to identify data streams that can benefit from more resources. our approach in this work is based on the relation between entropy, compression and gambling, extensively studied in information theory. it has been shown that in some settings entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. viewing online problem with stochastic input as an iterative gambling game, our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. we study bounds based on entropy for three online problems &mdash; list accessing, prefetching and caching. we show that entropy is a good performance characterizer for prefetching, but not so good characterizer for online caching.
efficient hashing with lookups in two memory accesses. the study of hashing is closely related to the analysis of balls and bins. azar et. al. [1] showed that instead of using a single hash function if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins. this leads to the concept of two-way hashing where the largest bucket contains o(log log n) balls with high probability. the hash look up will now search in both the buckets an item hashes to. since an item may be placed in one of two buckets, we could potentially move an item after it has been initially placed to reduce maximum load. using this fact, we present a simple, practical hashing scheme that maintains a maximum load of 2, with high probability, while achieving high memory utilization. in fact, with n buckets, even if the space for two items are pre-allocated per bucket, as may be desirable in hardware implementations, more than n items can be stored giving a high memory utilization. assuming truly random hash functions, we prove the following properties for our hashing scheme.&bull; each lookup takes two random memory accesses, and reads at most two items per access.&bull; each insert takes o(log n) time and up to log log n+o(1) moves, with high probability, and constant time in expectation.&bull; maintains 83.75% memory utilization, without requiring dynamic allocation during inserts.we also analyze the trade-off between the number of moves performed during inserts and the maximum load on a bucket. by performing at most h moves, we can maintain a maximum load of o(log log n/h log (log log n/h)). so, even by performing one move, we achieve a better bound than by performing no moves at all.
self-testing polynomial functions efficiently and over rational domains. in this paper we give the first self-testers and checkers for polynomials over rational and integer domains. we also show significantly stronger bounds on the efficiency of a simple modification of the algorithm for self-testing polynomials over finite fields given in [8].
entropy based nearest neighbor search in high dimensions. in this paper we study the problem of finding the approximate nearest neighbor of a query point in the high dimensional space, focusing on the euclidean space. the earlier approaches use locality-preserving hash functions (that tend to map nearby points to the same value) to construct several hash tables to ensure that the query point hashes to the same bucket as its nearest neighbor in at least one table. our approach is different - we use one (or a few) hash table and hash several randomly chosen points in the neighborhood of the query point showing that at least one of them will hash to the bucket containing its nearest neighbor. we show that the number of randomly chosen points in the neighborhood of the query point q required depends on the entropy of the hash value h(p) of a random point p at the same distance from q at its nearest neighbor, given q and the locality preserving hash function h chosen randomly from the hash family. precisely, we show that if the entropy i(h(p)|q, h) = m and g is a bound on the probability that two far-off points will hash to the same bucket, then we can find the approximate nearest neighbor in o(np) time and near linear &otilde;(n) space where p = m/log(1/g). alternatively we can build a data structure of size &otilde;(n1/(1-p)) to answer queries in &otilde;(d) time. by applying this analysis to the locality preserving hash functions in [17, 21, 6] and adjusting the parameters we show that the c nearest neighbor can be computed in time &otilde;(np) and near linear space where p &ap; 2.06/c as c becomes large.
game theory, algorithms, and the internet. among the many characteristics of the internet (huge and growing, available and unstructured, dynamic and chaotic), perhaps the most novel, distinguishing, and intellectually challenging one is that, unlike previous computational artifacts and systems, the internet is built, operated, and used by a dazzling diversity of economic interests, in various degrees of collaboration and competition with each other. consequently, it can be argued that the mathematical arsenal necessary for attaining an algorithmic and conceptual understanding of the internet must include some kind of fusion between mathematical economics (especially game theory and its inverse problem, mechanism design) and algorithmic thinking. in this talk i shall survey recent formalisms and results aiming in this general direction, and discuss the research agenda that appears to be emerging.
the vertex-disjoint menger problem in planar graphs. we consider the problem of finding a maximum collection of vertex-disjoint paths in undirected, planar graphs from a vertex $s$ to a vertex $t$. this problem is usually solved using flow techniques, which lead to ${\cal o}(nk)$ and ${\cal o}(n\sqrt{n})$ running times, respectively, where $n$ is the number of vertices and $k$ the maximum number of vertex-disjoint $(s,t)$-paths. the best previously known algorithm is based on a divide-and-conquer approach and has running time ${\cal o}(n\log n)$. the approach presented here is completely different from these methods and yields a linear-time algorithm.
computing equilibria in multi-player games. we initiate the systematic study of algorithmic issues involved in finding equilibria (nash and correlated) in games with a large number of players; such games, in order to be computationally meaningful, must be presented in some succinct, game-specific way. we develop a general framework for obtaining polynomial-time algorithms for optimizing over correlated equilibria in such settings, and show how it can be applied successfully to symmetric games (for which we actually find an exact polytopal characterization), graphical games, and congestion games, among others. we also present complexity results implying that such algorithms are not possible in certain other such games. finally, we present a polynomial-time algorithm, based on quantifier elimination, for finding a nash equilibrium in symmetric games when the number of strategies is relatively small.
multi-dimensional online tracking. we propose and study a new class of online problems, which we call online tracking. suppose an observer, say alice, observes a multi-valued function f: z+ &rarr; zd overtime in an online fashion, i.e., she only sees f(t) for t &le; tnow where tnow is the current time. she would like to keep a tracker, say bob, informed of the current value of f at all times. under this setting, alice could send new values of f to bob from time to time, so that the current value of f is always within a distance of &delta; to the last value received by bob. we give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire f in advance. we also consider variations of the problem where alice is allowed to send "predictions" to bob, to further reduce communication for well-behaved functions. these online tracking problems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems.
the complexity of low-distortion embeddings between point sets. we prove that it is np-hard to approximate by a ratio better than 3 the minimum distortion of a bijection between two given finite three-dimensional sets of points.
a faster and simpler fully dynamic transitive closure. we obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. our algorithm maintains the transitive closure matrix in a total running time of o(mn &plus; (ins &plus; del) &middot; n2), where ins (del) is the number of insert (delete) operations performed. here n is the number of vertices in the graph and m is the initial number of edges in the graph. obviously, reachability queries can be answered in constant time. the algorithm uses only o(n2) time which is essentially optimal for maintaining the transitive closure matrix. our algorithm can also support path queries. if v is reachable from u, the algorithm can produce a path from u to v in time proportional to the length of the path. the best previously known algorithm for the problem is due to demetrescu and italiano [2000]. their algorithm has a total running time of o(n3 &plus; (ins &plus; del) &middot; n2). the query time is also constant. in addition, we also present a simple algorithm for directed acyclic graphs (dags) with a total running time of o(mn &plus; ins &middot; n2 &plus; del). our algorithms are obtained by combining some new ideas with techniques of italiano [1986, 1988], king [1999], king and thorup [2001] and frigioni et al. [2001]. we also note that our algorithms are extremely simple and can be easily implemented.
a new and simple algorithm for quality 2-dimensional mesh generation. we present a simple new algorithm for triangulating polygons and planar straightline graphs. it provides "shape" and "size" guarantees: -all triangles have a bounded aspect ratio. - the number of "steiner points" added is within a constant factor of optimal. such "quality" triangulations are desirable as meshes for the finite element method, in which the running time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. the technique we use--successive refinement of the delaunay triangulation--extends a mesh generation technique of chew by allowing triangles that vary in size. previous algorithms with shape and size bounds have all been based on quadtrees. the delaunay refinement algorithm matches their bounds, but uses a fundamentally different approach. it is much simpler, and hence easier to implement, and it generally produces smaller meshes in practice.
edge dominating and hypomatchable sets. the weighted edge dominating set problem (eds) generalizes both the weighted vertex cover problem and the problem of covering the edges of graph by a minimum cost set of both vertices and edges. although eds was proven np-complete in 1980, not much progress had been made in improving its approximability to match that of weighted vertex cover until 2000. in this paper we develop a 2-approximation for weighted eds by honing the technique of a recent 2 1/10-approximation which exploits the close polyhedral relationship between eds and the edge cover problem. for the sake of completeness we also present a new direct proof of edmonds and johnson's characterization of the edge cover polyhedron. our approximation guarantee is tight in the sense that the existence of a (2-&epsilon;)-approximation for weighted eds for some constant, &epsilon; would imply a (2-&epsilon;)-approximation for weighted vertex cover, constituting a major breakthrough in the field.
succinct representations of lcp information and improvements in the compressed suffix arrays. we introduce two succinct data structures to solve various string problems. one is for storing the information of lcp, the longest common prefix, between suffixes in the suffix array, and the other is an improvement in the compressed suffix array which supports linear time counting queries for any pattern. the former occupies only 2n + o(n) bits for a text of length n for computing lcp between adjacent suffixes in lexicographic order in constant time, and 6n + o(n) bits between any two suffixes. no data structure in the literature attained linear size. the latter has size proportional to the text size and it is applicable to texts on any alphabet &sigma; such that |&sigma;| = logo(1) n. these space-economical data structures are useful in processing huge amounts of text data.
towards a complete characterization of tries. tries and suffix trees are the most popular data structures on words. tries were introduced in 1960 by fredkin as an efficient method for searching and sorting digital data. since then myriad of novel trie applications were found such as dynamic hashing, conflict resolution algorithms, leader election algorithms, ip addresses lookup, coding, polynomial factorization, lempel-ziv compression schemes, and so on. furthermore, various analyses of tries reveal new fundamental properties of strings appearing in those applications. parameters of interest are the (partial) fillup level (the largest full level of the trie), shortest path, height (longest path), typical depth, and path length (sum of depths). all of these parameters are analyzed here in a unifying manner by studying the external and internal profiles. a profile of a tree at level k is the number of nodes (internal or external) at level k. we derive recurrences for both profiles and solve them asymptotically for various ranges of k when the strings stored in the trie are generated by a memoryless source (extension to a markov source is possible). in particular, we present asymptotic results for the average profile, the variance and the limiting distribution. as consequences we find the height, shortest path, fillup level, and the depth. these results are derived here by methods of analytic algorithmics such as generating functions, mellin transform, poissonization and depoissonization, and the saddle point method.
squeezing succinct data structures into entropy bounds. consider a sequence s of n symbols drawn from an alphabet a = {1, 2,. . .,&sigma;}, stored as a binary string of nlog &sigma; bits. a succinct data structure on s supports a given set of primitive operations on s using just f (n) = o(n log &sigma;) extra bits. we present a technique for transforming succinct data structures (which do not change the binary content of s) into compressed data structures using nhk + f(n) + o(n log &sigma; + log log&sigma; n + k)/ log&sigma; n) bits of space, where hk &le; log &sigma; is the kth-order empirical entropy of s. when k + log &sigma; = o(log n), we improve the space complexity of the succinct data structure from n log &sigma; + o(n log &sigma;) to n hk + o(nlog &sigma;) bits by keeping s in compressed format, so that any substring of o(log &sigma; n) symbols in s (i.e. o(log n) bits) can be decoded on the fly in constant time. thus, the time complexity of the supported operations does not change asymptotically. namely, if an operation takes t(n) time in the succinct data structure, it requires o(t(n)) time in the resulting compressed data structure. using this simple approach we improve the space complexity of some of the best known results on succinct data structures we extend our results to handle another definition of entropy.
optimal binary space partitions for orthogonal objects. a binary space partition, or bsp is a scheme for recursively dividing a configuration of objects by hyperplanes until all objects are separated. bsps are widely used in computer graphics as the underlying data structure for computations such as real-time hidden-surface removal, ray tracing, and solid modelling. in these applications, the computational cost is directly related to the size of the bsp, ie the toal number of fragments of the objects generated by the partition. until recently, the question of minimizing the size of bsps for given inputs had been studied only empirically. we concentrate here on ortogonal objects, a case which arises frequently in practice and deserves special attention. we construct bsps of linear size for any set of orthogonal line segments in the plane. in three dimensions, bsps of size o(n^1.5) for any set of n mutually orthogonal line segments or rectangles are constructed. these bounds are optimal and may be contrasted with the omega(n^2) bound for general polygonal objects in r^3.
overhang. how far off the edge of the table can we reach by stacking n identical blocks of length 1? a classical solution achieves an overhang of 1/2hn, where hn = &sigma;ni=1 1/i ~ ln n is the nth harmonic number, by stacking all the blocks one on top of another with the ith block from the top displaced by 1/2i beyond the block below. this solution is widely believed to be optimal. we show that it is exponentially far from optimal by giving explicit constructions with an overhang of &omega;(n1/3). we also prove some upper bounds on the overhang that can be achieved. the stability of a given stack of blocks corresponds to the feasibility of a linear program and so can be efficiently determined.