waashk/dblp huggingface dataset:
paging and list update under bijective analysis. it has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms which achieve the same competitive ratio, ranging from extremely naive and inefficient strategies (such as flush-when-full), to strategies of excellent performance in practice (such as least-recently-used and some of its variants). a similar situation arises in the list update problem: in particular, under the cost formulation studied by mart&iacute;nez and roura [tcs 2000] and munro [esa 2000] every list update algorithm has, asymptotically, the same competitive ratio. several refinements of competitive analysis, as well as alternative performance measures have been introduced in the literature, with varying degrees of success in narrowing this disconnect between theoretical analysis and empirical evaluation. in this paper we study these two fundamental online problems under the framework of bijective analysis [angelopoulos, dorrigiv and l&oacute;pez-ortiz, soda 2007 and latin 2008]. this is an intuitive technique which is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. coupled with a well-established model of locality of reference due to albers, favrholdt and giel [jcss 2005], we show that least-recently-used and move-to-front are the unique optimal algorithms for paging and list update, respectively. prior to this work, only measures based on average-cost analysis have separated lru and mtf from all other algorithms. given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense lru and mtf stand out as the best algorithms.
robust pca and clustering in noisy mixtures. this paper presents a polynomial algorithm for learning mixtures of logconcave distributions in rn in the presence of malicious noise. that is, each sample is corrupted with some small probability, being replaced by a point about which we can make no assumptions. a key element of the algorithm is robust principle components analysis (pca), which is less susceptible to corruption by noisy points. while noise may cause standard pca to collapse well-separated mixture components so that they are indistinguishable, robust pca preserves the distance between some of the components, making a partition possible. it then recurses on each half of the mixture until every component is isolated. the success of this algorithm requires only a o(log n) factor increase in the required separation between components of the mixture compared to the noiseless case.
optimality of belief propagation for random assignment problem. the assignment problem concerns finding the minimum-cost perfect matching in a complete weighted n x n bipartite graph. any algorithm for this classical question clearly requires &omega;(n2) time, and the best known one (edmonds and karp, 1972) finds solution in o(n3). for decades, it has remained unknown whether optimal computation time is closer to n3 or n2. we provide answer to this question for random instance of assignment problem. specifically, we establish that belief propagation finds solution in o(n2) time when edge-weights are i.i.d. with light tailed distribution.
linear-time algorithms for geometric graphs with sublinearly many crossings. we provide linear-time algorithms for geometric graphs with sublinearly many crossings. that is, we provide algorithms running in o(n) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated logarithmic factor. specific problems we study include voronoi diagrams and single-source shortest paths. our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. instead, our algorithms are based on a planarization method that "zeroes in" on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. incidentally, our planarization algorithm also solves an open computational geometry problem of chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.
constructing laplace operator from point clouds in . we present an algorithm for approximating the laplace-beltrami operator from an arbitrary point cloud obtained from a k-dimensional manifold embedded in the d-dimensional space. we show that this pcd laplace (point-cloud data laplace) operator converges to the laplace-beltrami operator on the underlying manifold as the point cloud becomes denser. unlike the previous work, we do not assume that the data samples are independent identically distributed from a probability distribution and do not require a global mesh. the resulting algorithm is easy to implement. we present experimental results indicating that even for point sets sampled from a uniform distribution, pcd laplace converges faster than the weighted graph laplacian. we also show that using our pcd laplacian we can directly estimate certain geometric invariants, such as manifold area.
how hard is it to approximate the best nash equilibrium? the quest for a ptas for nash equilibrium in a two-player game seeks to circumvent the ppad-completeness of an (exact) nash equilibrium by finding an approximate equilibrium, and has emerged as a major open question in algorithmic game theory. a closely related problem is that of finding an equilibrium maximizing a certain objective, such as the social welfare. this optimization problem was shown to be np-hard by gilboa and zemel [games and economic behavior 1989]. however, this np-hardness is unlikely to extend to finding an approximate equilibrium, since the latter admits a quasi-polynomial time algorithm, as proved by lipton, markakis and mehta [proc. of 4th ec, 2003]. we show that this optimization problem, namely, finding in a two-player game an approximate equilibrium achieving large social welfare is unlikely to have a polynomial time algorithm. one interpretation of our results is that the quest for a ptas for nash equilibrium should not extend to a ptas for finding the best nash equilibrium, which stands in contrast to certain algorithmic techniques used so far (e.g. sampling and enumeration). technically, our result is a reduction from a notoriously difficult problem in modern combinatorics, of finding a planted (but hidden) clique in a random graph g(n, 1/2). our reduction starts from an instance with planted clique size k = o(log n). for comparison, the currently known algorithms due to alon, krivelevich and sudakov [random struct. & algorithms, 1998], and krauthgamer and feige [random struct. & algorithms, 2000], are effective for a much larger clique size k = &omega;(&radic;n).
monotone minimal perfect hashing: searching a sorted table with (1) accesses. a minimal perfect hash function maps a set s of n keys into the set {0, 1,..., n -- 1} bijectively. classical results state that minimal perfect hashing is possible in constant time using a structure occupying space close to the lower bound of log e bits per element. here we consider the problem of monotone minimal perfect hashing, in which the bijection is required to preserve the lexicographical ordering of the keys. a monotone minimal perfect hash function can be seen as a very weak form of index that provides ranking just on the set s (and answers randomly outside of s). our goal is to minimise the description size of the hash function: we show that, for a set s of n elements out of a universe of 2w elements, o(n log log w) bits are sufficient to hash monotonically with evaluation time o(log w). alternatively, we can get space o(n log w) bits with o(1) query time. both of these data structures improve a straightforward construction with o(n log w) space and o(log w) query time. as a consequence, it is possible to search a sorted table with o(1) accesses to the table (using additional o(n log log w) bits). our results are based on a structure (of independent interest) that represents a trie in a very compact way, but admits errors. as a further application of the same structure, we show how to compute the predecessor (in the sorted order of s) of an arbitrary element, using o(1) accesses in expectation and an index of o(n log w) bits, improving the trivial result of o(n w) bits. this implies an efficient index for searching a blocked memory.
line transversals of convex polyhedra in . we establish a bound of o(n2k1+&epsilon;), for any &epsilon; > 0, on the combinatorial complexity of the set t of line transversals of a collection p of k convex polyhedra in r3 with a total of n facets, and present a randomized algorithm which computes the boundary of t in comparable expected time. thus, when k &lt; n, the new bounds on the complexity (and construction cost) of t improve upon the previously best known bounds, which are nearly cubic in n. to obtain the above result, we study the set tl0 of line transversals which emanate from a fixed line l0, establish an almost tight bound of o(nk1+&epsilon;) on the complexity of tl0, and provide a randomized algorithm which computes tl0 in comparable expected time. slightly improved combinatorial bounds for the complexity of tl0, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of p are pairwise disjoint: the case where l0 is disjoint from the polyhedra of p, and the case where the polyhedra of p are unbounded in a direction parallel to l0.
the complexity of simulating brownian motion. we analyze the complexity of the walk on spheres algorithm for simulating brownian motion in a domain &omega; &sub;rd. the algorithm, which was first proposed in the 1950s, produces samples from the hitting probability distribution of the brownian motion process on &part;&omega; within an error of &epsilon;. the algorithm is used as a building block for solving a variety of differential equations, including the dirichlet problem. the wos algorithm simulates a bm starting at a point x0 = x in a given bounded domain &omega; until it gets &epsilon;-close to the boundary &part;&omega;. at every step, the algorithm measures the distance dk from its current position xk to &part;&omega; and jumps a distance of dk/2 in a uniformly random direction from xk to obtain xk+1. the algorithm terminates when it reaches xn that is &epsilon;-close to &part;&omega;. it is not hard to see that the algorithm requires at least &omega;(log 1/&epsilon;) steps to converge. only partial results with respect to the upper bound existed. in 1959 m. motoo established an o(log 1/&epsilon;) bound on the running time for convex domains. the results were later generalized for a wider, but still very restricted, class of planar and 3-dimensional domains by g. a. mikhailov (1979). in our earlier work (2007), we established an upper bound of o(log2 1/&epsilon;) on the rate of convergence of wos for arbitrary planar domains. in this paper we introduce energy functions using newton potentials to obtain very general upper bounds on the convergence of the algorithm. special instances of the upper bounds yield the following results for bounded domains &omega;. &bull; if &omega; is a planar domain with connected exterior, the wos converges in o(log 1/&epsilon;) steps; &bull; if &omega; is a domain in r3 with connected exterior, the wos converges in o(log2 1/&epsilon;) steps; &bull; for d > 2, if &omega; is a domain in rd, the wos converges in o((1/&epsilon;)2-4/d) steps; &bull; for d > 3, if &omega; is a domain in rd with connected exterior, the wos converges in o((1/&epsilon;)2--4/(d--1)) steps; &bull; for any d, if &omega; is a domain in rd bounded by a smooth surface &part;&omega;, the wos converges in o(log 1/&epsilon;) steps. we also demonstrate that the bounds are tight, i.e. we construct a domain from each class for which the upper bound is exact. our results give the optimal upper bound of o(log 1/&epsilon;) in many cases for which only a bound polynomial in 1/&epsilon; was previously known.
termination criteria for solving concurrent safety and reachability games. we consider concurrent games played on graphs. at every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. we present in this paper a strategy improvement algorithm for computing the value of a concurrent safety game, that is, the maximal probability with which player 1 can enforce the safety objective. the algorithm yields a sequence of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the safety game. our result is significant because the strategy improvement algorithm provides, for the first time, a way to approximate the value of a concurrent safety game from below. since a value iteration algorithm, or a strategy improvement algorithm for reachability games, can be used to approximate the same value from above, the combination of both algorithms yields a method for computing a converging sequence of upper and lower bounds for the values of concurrent reachability and safety games. previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.
on the complexity of nash equilibria of action-graph games. in light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of nash equilibria yet remains as expressive as possible, we investigate the computational complexity of nash equilibria in the recently proposed model of action-graph games (aggs). aggs, introduced by bhat and leyton-brown, are succinct representations of games that encapsulate both local dependencies as in graphical games, and partial indifference to other agents' identities as in anonymous games, which occur in many natural settings such as financial markets. this is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. we present a simple fully polynomial time approximation scheme for computing mixed nash equilibria of aggs with constant degree, constant treewidth and a constant number of agent types (but an arbitrary number of strategies), and extend this algorithm to a broader set of instances. however, the main results of this paper are negative, showing that when either of the latter conditions are relaxed the problem becomes intractable. in particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is np- complete to decide the existence of a pure-strategy nash equilibrium and ppad-complete to compute a mixed nash equilibrium (even an approximate one). similarly for aggs with a constant number of agent types but unconstrained treewidth. these hardness results suggest that, in some sense, our fptas is as strong a positive result as one can expect. in the broader context of trying to pin down the boundary where the equilibria of multi-player games can be computed efficiently, these results complement recent hardness results for graphical games and algorithmic results for anonymous games.
combinatorial algorithms for wireless information flow. a long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. the difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. recently, avestimehr, diggavi and tse proposed a linear binary deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. they generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. they showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. however, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes infeasible. in this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in binary linear deterministic (wireless) networks, for the case of a unicast connection. our algorithm crucially uses a notion of linear independence between edges to calculate the capacity in polynomial time. moreover, we can achieve the capacity by using very simple onebit processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
improved approximation algorithms for scheduling with fixed jobs. we study two closely related problems in non-preemptive scheduling of sequential jobs on identical parallel machines. in these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in either case, the objective is to minimize the makespan. both formulations have different applications, e.g. in turnaround scheduling or overlay computing. for both problems we contribute approximation algorithms with an improved ratio of 3/2 + &epsilon;, respectively. for scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by scharbrodt, steger & weisser; for scheduling with non-availability we provide the same lower bound. in total, our approximation ratio for both problems is essentially tight via suitable inapproximability results. we use dual approximation, creation of a gap structure and job configurations, and a ptas for the multiple subset sum problem. however, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to large gaps.
a generic top-down dynamic-programming approach to prefix-free coding. given a probability distribution over a set of n words to be transmitted, the huffman coding problem is to find a minimal-cost prefix free code for transmitting those words. the basic huffman coding problem can be solved in o(n log n) time but variations are more difficult. one of the standard techniques for solving these variations utilizes a top-down dynamic programming approach. in this paper we show that this approach is amenable to dynamic programming speedup techniques, permitting a speedup of an order of magnitude for many algorithms in the literature for such variations as mixed radix, reserved length and one-ended coding. these speedups are immediate implications of a general structural property that permits batching together the calculation of many dp entries.
on the bit-complexity of lempel-ziv compression. one of the most famous and investigated lossless data-compression schemes is the one introduced by lempel and ziv about 30 years ago [37]. this compression scheme is known as "dictionary-based compressor" and consists of squeezing an input string by replacing some of its substrings with (shorter) codewords which are actually pointers to a dictionary of phrases built as the string is processed. surprisingly enough, although many fundamental results are nowadays known about the speed and effectiveness of this compression process (see e.g. [23, 28] and references therein), "we are not aware of any parsing scheme that achieves optimality when the lz77-dictionary is in use under any constraint on the codewords other than being of equal length" [28, pag. 159]. here optimality means to achieve the minimum number of bits in compressing each individual input string, without any assumption on its generating source. in this paper we investigate three issues pertaining to the bit-complexity of lz-based compressors, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. these theoretical results will be sustained by some experiments that will compare our novel lz-based compressors against the most popular compression tools (like gzip, bzip2) and state-of-the-art compressors (like the booster of [14, 13]).
efficient algorithms on sets of permutations, dominance, and real-weighted apsp. sets of permutations play an important role in the design of some efficient algorithms. in this paper we design two algorithms that manipulate sets of permutations. both algorithms, each solving a different problem, use fast matrix multiplication techniques to achieve a significant improvement in the running time over the naive solutions. for a set of permutations p &sub; sn we say that i k-dominates j if the number of permutations &pi; &isin; p for which &pi;(i) < &pi;(j) is k. the dominance matrix of p is the n x n matrix dp where dp(i, j) = k if and only if i k-dominates j. we give an efficient algorithm for computing dp using fast rectangular matrix multiplication. in particular, when |p| = n our algorithm runs in o(n2.684) time. computing the dominance matrix of permutations is computationally equivalent to the dominance problem in computational geometry. thus, our algorithm slightly improves upon a well-known o(n2.688) time algorithm of matousek for the dominance problem. permutation dominance is used, together with several other ingredients, to obtain a truly sub-cubic algorithm for the all pairs shortest paths (apsp) problem in real-weighted directed graphs, where the number of distinct weights emanating from each vertex is o(n0.338). a special case of this algorithm implies an o(n2.842) time algorithm for real vertex-weighted apsp, which slightly improves a recent result of chan [stoc-07]. a set of permutations p &sub; sn is fully expanding if the product of any two elements of p yields a distinct permutation. stated otherwise, |p2| = |p|2 where p2 &sub; sn is the set of products of two elements of p. we present a randomized algorithm that computes |p2| and hence decides if p is fully expanding. the algorithm also produces a table that, for any &sigma;1, &sigma;2, &sigma;3, &sigma;4 &isin; p, answers the query &sigma;1&sigma;2 = &sigma;3&sigma;4 in &otilde;(1) time. the algorithm uses, among other ingredients, a combination of fast matrix multiplication and polynomial identity testing. in particular, for |p| = n our algorithm runs in o(n&omega;) time where &omega; < 2.376 is the matrix multiplication exponent. we note that the naive deterministic solution for this problem requires &theta;(n3) time.
size complexity of volume meshes vs. surface meshes. typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. the surface mesh may be uniformly spaced or highly graded, and may have fine resolution due to extrinsic mesh size concerns. when we desire that such a volume mesh have good aspect ratio, we require that some space-filling scaffold vertices be inserted off the surface. we analyze the number of scaffold vertices in a setting that encompasses many existing volume meshing algorithms. we show that under simple preconditions, the number of scaffold vertices will be linear in the number of surface vertices.