waashk/dblp huggingface dataset:
the cover time of two classes of random graphs. let g = (v,e) be a connected graph, let |v| = n, and |e| = m. a random walk wu, u &isin; v on the undirected graph g = (v, e) is a markov chain x0 = u, x1,...xt,... &isin; v associated to a particle that moves from vertex to vertex according to the following rule: the probability of a transition from vertex i, of degree di, to vertex j is 1/di if {i,j} &isin; e, and 0 otherwise. for u &isin; v let cu be the expected time taken for wu to visit every vertex of g. the cover time cg of g is defined as cg = maxu&isin;v cu. the cover time of connected graphs has been extensively studied. it is a classic result of aleliunas, karp, lipton, lov&aacute;sz and rackoff [2] that cg &le; 2m(n - 1). it was shown by feige [11], [12], that for any connected graph g[equation]the lower bound is achieved by (for example) the complete graph kn, whose cover time is determined by the coupon collector problem.
a note on random 2-sat with prescribed literal degrees. two classic "phase transitions" in discrete mathematics are the emergence of a giant component in a random graph as the density of edges increases, and the transition of a random 2-sat formula from satisfiable to unsatisfiable as the density of clauses increases. the random-graph result has been extended to the case of prescribed degree sequences, where the almost-sure nonexistence or existence of a giant component is related to a simple property of the degree sequence. we similarly extend the satisfiability result, by relating the almost-sure satisfiability or unsatisfiability of a random 2-sat formula to an analogous property of a prescribed literal sequence.
sparse source-wise and pair-wise distance preservers. we introduce and study the notions of pair-wise and source-wise preservers.given an undirected n-vertex graph g = (v, e) and a subset p of pairs of vertices, let g' = (v, h), h &sube; e, be called a pair-wise preserver of g with respect to p if for every pair {u, w} &isin; p, distg' (u, w) = distg (u, w). for a set s &sube; v of sources, a pair-wise preserver of g with respect to the set of all pairs p = (s/2) of sources is called a source-wise preserver of g with respect to s.we prove that for every undirected possibly weighted n-vertex graph g and every subset p of p = o(n1/2) pairs of vertices of g, there exists a linear-size pair-wise preserver of g with respect to p. consequently, for every subset s &sube; v of s = o(n1/4) sources, there exists a linear-size source-wise preserver of g with respect to s. on the negative side we show that neither of the two exponents (1/2 and 1/4) can be improved even when the attention is restricted to unweighted graphs.our lower bounds involve constructions of dense convexly independent sets of vectors with small euclidean norms. we believe that the link between the areas of discrete geometry and spanners that we establish is of independent interest, and might be useful in the study of other problems in the area of low-distortion embeddings.
ordering by weighted number of wins gives a good ranking for weighted tournaments. we consider the following simple algorithm for feedback arc set problem in weighted tournaments: order the vertices by their weighted indegrees. we show that this algorithm has an approximation guarantee of 5 if the weights satisfy probability constraints (for any pair of vertices u and v, wuv+wvu&equals;1). special cases of the feedback arc set problem in such weighted tournaments include the feedback arc set problem in unweighted tournaments and rank aggregation. to complement the upper bound, for any constant &epsi;>0, we exhibit an infinite family of (unweighted) tournaments for which the aforesaid algorithm (irrespective of how ties are broken) has an approximation ratio of 5-&epsi;.
random max sat, random max cut, and their phase transitions. with random inputs, certain decision problems undergo a &ldquo;phase transition.&rdquo; we prove similar behavior in an optimization context. given a conjunctive normal form (cnf) formula f on n variables and with m k-variable clauses, denote by max f the maximum number of clauses satisfiable by a single assignment of the variables. (thus the decision problem k-sat is to determine if max f is equal to m.) with the formula f chosen at random, the expectation of max f is trivially bounded by (3&#x002f;4)m &les; &eopf; max f &les; m. we prove that for random formulas with m = &lfloor;cn&rfloor; clauses: for constants c < 1, &eopf; max f is &lfloor;cn&rfloor; - &theta;(1&#x002f;n); for large c, it approaches ** equation here ** and in the &ldquo;window&rdquo; c = 1 + &theta;(n-1&#x002f;3), it is cn - &theta;(1). our full results are more detailed, but this already shows that the optimization problem max 2-sat undergoes a phase transition just as the 2-sat decision problem does, and at the same critical value c = 1. most of our results are established without reference to the analogous propositions for decision 2-sat, and can be used to reproduce them. we consider &ldquo;online&rdquo; versions of max 2-sat, and show that for one version the obvious greedy algorithm is optimal; all other natural questions remain open. we can extend only our simplest max 2-sat results to max k-sat, but we conjecture a &ldquo;max k-sat limiting function conjecture&rdquo; analogous to the folklore &ldquo;satisfiability threshold conjecture,&rdquo; but open even for k = 2. neither conjecture immediately implies the other, but it is natural to further conjecture a connection between them. we also prove analogous results for random max cut. &copy; 2004 wiley periodicals, inc. random struct. alg., 2004
the diameter of a long range percolation graph. we consider the following long-range percolation model: an undirected graph with the node set {0, 1, ..., n}d, has edges (x, y) selected with probability ≈ β/||x -y||s if ||x - y|| < 1, and with probability 1 if ||x - y|| = 1, for some parameters β, s < 0. this model was introduced by benjamini and berger [2], who obtained bounds on the diameter of this graph for the one-dimensional case d = 1 and for various values of s, but left cases s = 1, 2 open. we show that, with high probability, the diameter of this graph is θ(log n/log log n) when s = d, and, for some constants 0 >' η1 > η2 > 1, it is at most nη2 when s = 2d, and is at least nη1 when d = 1, s = 2, β > 1 or when s > 2d. we also provide a simple proof that the diameter is at most log o(1) n with high probability, when d > s > 2d, established previously in [2].
an improved data stream algorithm for frequency moments. we present a simple, one-pass, &otilde;(&radic;n)-space data stream algorithm for approximating the third frequency moment. this is the first improvement to the &otilde;(n2/3)-space data stream algorithm of alon, matias, and szegedy [ams99]. the current known lower bound for this problem is &omega;(n1/3) [bjks02a].our algorithm can also be generalized to an &otilde;(n1-1/(k-1))-space data stream algorithm for approximating the k-th frequency moment. besides improving the &otilde;(n1--1/k)-space upper bound [ams99], our algorithm beats the &omega;(n1--1/k)-sampling lower bound [bks01] for this problem.our method suggests a unified perspective of space-efficient data stream algorithms for all frequency moments.
the string edit distance matching problem with moves. the edit distance between two strings s and r is defined to be the minimum number of character inserts, deletes, and changes needed to convert r to s. given a text string t of length n, and a pattern string p of length m, informally, the string edit distance matching problem is to compute the smallest edit distance between p and substrings of t. we relax the problem so that: (a) we allow an additional operation, namely, substring moves; and (b) we allow approximation of this string edit distance. our result is a near-linear time deterministic algorithm to produce a factor of o(log n log&ast; n) approximation to the string edit distance with moves. this is the first known significantly subquadratic algorithm for a string edit distance problem in which the distance involves nontrivial alignments. our results are obtained by embedding strings into l1 vector space using a simplified parsing technique, which we call edit-sensitive parsing (esp).
substring compression problems. we initiate a new class of string matching problems called substring compression problems. given a string s that may be preprocessed, the problem is to quickly find the compressed representation or the compressed size of any query substring of s (substring compression query or scq) or to find the length l substring of s whose compression is the least (least compressible substring or lcs problem).starting from the seminal paper of lempel and ziv over 25 years ago, many different methods have emerged for compressing entire strings. determining substring compressibility is a natural variant that is combinatorially and algorithmically challenging, yet surprisingly has not been studied before. in addition, compressibility of strings is emerging as a tool to compare biological sequences and analyze their information content. however, typically, the compressibility of the entire sequence is not as informative as that of portions of the sequences. thus substring compressibility may be a more suitable basis for sequence analysis.we present the first known, nearly optimal algorithms for substring compression problems---scq, lcs and their generalizations---that are exact or provably approximate. our exact algorithms exploit the structure in strings via suffix trees and our approximate algorithms rely on new relationships we find between lempel-ziv compression and string parsings.
communication complexity of document exchange. we have two users, a and b, who hold documents x and y respectively. neither of the users has any information about the other''s document. they exchange messages so that b computes x; it may be required that a compute y as well. our goal is to design communication protocols with the main objective of minimizing the total number of bits they exchange; other objectives are minimizing the number of rounds and the complexity of internal computations. an important notion which determines the efficiency of the protocols is how one measures the distance between x and y. we consider several metrics for measuring this distance, namely the hamming metric, the levenshtein metric (edit distance), and a new lz metric, which is introduced in this paper. we show how to estimate the distance between x and y using a single message of logarithmic size. for each metric, we present the first communication-efficient protocols, which often match the corresponding lower bounds. a consequence of these are error-correcting codes for these error models which correct up to d errors in n characters using o(d log n) bits. our most interesting methods use a new histogram transformation that we introduce to convert edit distance to l1 distance.
approximation schemes for multidimensional packing. we consider a classic multidimensional generalization of the bin packing problem, namely, packing d-dimensional rectangles into the minimum number of unit cubes. our two results are: an asymptotic polynomial time approximation scheme for packing d-dimensional cubes into the minimum number of unit cubes and a polynomial time algorithm for packing rectangles into at most opt bins whose sides have length (1 + ε), where opt denotes the minimum number of unit bins required to pack the rectangles. both algorithms also achieve the best possible additive constant term. for cubes, this settles the approximability of the problem and represents a significant improvement over the previous best known asymptotic approximation factor of 2 - (2/3)d + ε. for rectangles, this contrasts with the currently best known approximation factor of 1.691....
a sub-quadratic sequence alignment algorithm for unrestricted cost matrices. the classical algorithm for computing the similarity between two sequences [36, 39] uses a dynamic programming matrix, and compares two strings of size n in o(n2) time. we address the challenge of computing the similarity of two strings in sub-quadratic time, for metrics which use a scoring matrix of unrestricted weights. our algorithm applies to both local and global alignment computations.the speed-up is achieved by dividing the dynamic programming matrix into variable sized blocks, as induced by lempel-ziv parsing of both strings, and utilizing the inherent periodic nature of both strings. this leads to an o(n2/log n) algorithm for an input of constant alphabet size. for most texts, the time complexity is actually o(hn2/log n) where h &le; 1 is the entropy of the text.
random walks on the vertices of transportation polytopes with constant number of sources. we consider the problem of uniformly sampling a vertex of a transportation polytope with m sources and n destinations, where m is a constant. we analyse a natural random walk on the edge-vertex graph of the polytope. the analysis makes use of the multicommodity flow technique of sinclair [20] together with ideas developed by morris and sinclair [15, 16] for the knapsack problem, and cryan et al. [2] for contingency tables, to establish that the random walk approaches the uniform distribution in time no(m2).
approximability of dense and sparse instances of minimum 2-connectivity, tsp and path problems. we study the approximability of dense and sparse instances of the following problems: the minimum 2-edge-connected (2-ec) and 2-vertex-connected (2-vc) spanning subgraph, metric tsp with distances 1 and 2 (tsp (1,2)), maximum path packing, and the longest path (cycle) problems. the approximability of dense instances of these problems was left open in arora et al. [3]. we characterize the approximability of all these problems by proving tight upper (approximation algorithms) and lower bounds (inapproximability). we prove that 2-ec, 2-vc and tsp (1,2) are max snp-hard even on 3-regular graphs, and provide explicit hardness constants, under p &ne; np. we also improve the approximation ratio for 2-ec and 2-vc on graphs with maximum degree 3. these are the first explicit hardness results on sparse and dense graphs for these problems. we apply our results to prove bounds on the integrality gaps of lp relaxations for dense and sparse 2-ec and tsp (1,2) problems, related to the famous metric tsp conjecture, due to goemans [17].
better approximation algorithms for bin covering. bin covering takes as input a list of items with sizes in (0, 1) and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. this is in a sense a dual problem to the classical one-dimensional bin packing problem, but has for many years lagged behind the latter in terms of the quality of the best approximation algorithms. we design algorithms for this problem that close the gap, both in terms of worst- and average-case results. we present (1) the first asymptotic approximation scheme for the offline version, (2) algorithms that have bounded worst-case behavior for instances with discrete item sizes and expected behavior that is asymptotically optimal for all discrete &ldquo;perfect-packing distributions&rdquo; (ones for which optimal packings have sublinear expected waste), and (3) a learning algorithm that has asymptotically optimal expected behavior for all discrete distributions. the algorithms of (2) and (3) are based on the recently-developed online sum-of-squares algorithm for bin packing. we also present experimental analysis comparing the algorithms of (2) and suggesting that one of them, the sum-of-squares-with-threshold algorithm, performs quite well even for discrete distributions that do not have the perfect-packing property.
chain decompositions and independent trees in 4-connected graphs. this work was motivated by the study of a multitree approach to reliability in distributed networks and by the study of non-separating paths and cycles in highly connected graphs. we first give a result on "non-separating chains" in 4-connected graphs. this result is then used to obtain a "non-separating chain decomposition" of a 4-connected graph g, and an o(&verbar;v(g)&verbar;2&verbar;e(g)&verbar;) algorithm for constructing such a decomposition. as an application of this decomposition, we show how to produce four "independent spanning trees" in a 4-connected graph in o(&verbar;v(g)&verbar;3) time.
sublinear-time approximation of euclidean minimum spanning tree. we consider the problem of finding the weight of a euclidean minimum spanning tree for a set of n points in ℝd. we focus on the situation when the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. we present an algorithm that estimates with high probability the weight of a euclidean minimum spanning tree of a set of points to within 1 + &epsilon; using only &otilde;(&radic; poly(1/&epsilon;)) queries for constant d. the algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbors queries.
approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. given an undirected graph, finding either a minimum 2-edge-connected spanning subgraph or a minimum 2-vertex-connected (biconnected) spanning subgraph is maxsnp-hard. we show that for planar graphs, both problems have a polynomial time approximation scheme (ptas) with running time no(1/ε), where n is the graph size and ε is the relative error allowed.when the planar graph has edge costs, we approximately solve the analogous min-cost subgraph problems in time no(&gamma;/ε), where &gamma; is the ratio of the total edge cost to the optimum solution cost.
soft kinetic data structures. we introduce the framework of soft kinetic data structures (skds). a soft kinetic data structure is an approximate data structure that can be used to answer queries on a set of moving objects with unpredictable motion. we analyze the quality of a soft kinetic data structure by giving a competitive analysis with respect to the dynamics of the system. we illustrate our approach by presenting soft kinetic data structures for maintaining classical data structures: sorted arrays, balanced search trees, heaps, and range trees. we also describe soft kinetic data structures for maintaining the euclidean minimum spanning trees.
tight bounds for worst-case equilibria. we study the problem of traffic routing in noncooperative networks. in such networks, users may follow selfish strategies to optimize their own performance measure and therefore, their behavior does not have to lead to optimal performance of the entire network. in this article we investigate the worst-case coordination ratio, which is a game-theoretic measure aiming to reflect the price of selfish routing. following a line of previous work, we focus on the most basic networks consisting of parallel links with linear latency functions. our main result is that the worst-case coordination ratio on m parallel links of possibly different speeds is &theta;(log m/log log log m). in fact, we are able to give an exact description of the worst-case coordination ratio, depending on the number of links and ratio of speed of the fastest link over the speed of the slowest link. for example, for the special case in which all m parallel links have the same speed, we can prove that the worst-case coordination ratio is &gamma;(&minus;1) (m) &plus; &theta;(1), with &gamma; denoting the gamma (factorial) function. our bounds entirely resolve an open problem posed recently by koutsoupias and papadimitriou [1999].
fast parallel algorithms for the clique separator decomposition. we give an efficient {\it nc} algorithm for finding a clique separator decomposition of an {\it arbitrary} graph, that is, a series of cliques whose removal disconnects the graph. this algorithm allows one to extend a large body of results which were originally formulated for chordal graphs to other classes of graphs. our algorithm is optimal to within a polylogarithmic factor of tarjan''s $o(mn)$ time sequential algorithm. the decomposition can also be used to find {\it nc} algorithms for some optimization problems on special families of graphs, assuming these problems can be solved in {\it nc} for the prime graphs of the decomposition. these optimization problems include: finding a maximum-weight clique, a minimum coloring, a maximum-weight independent set, and a minimum fill-in elimination order. we also give the first parallel algorithms for solving these problems by using the clique separator decomposition. our maximum-weight independent set algorithm applied to chordal graphs yields the most efficient known parallel algorithm for finding a maximum-weight independent set of a chordal graph.
an algorithm for counting maximum weighted independent sets and its applications. we present an o(1.3247n) algorithm for counting the number of independent sets with maximum weight in graphs. we show how this algorithm can be used solving a number of different counting problems: counting exact covers, exact hitting sets, weighted set packing and satisfying assignments in 1-in-k sat.
an exact subexponential-time lattice algorithm for asian options. asian options are path-dependent derivatives. how to price them efficiently and accurately has been a long-standing research and practical problem. asian options can be priced on the lattice. but only exponential-time algorithms are currently known if such options are to be priced on a lattice without approximation. although efficient approximation methods are available, most of them lack accuracy guarantees. this paper proposes a novel lattice for pricing asian options. the resulting exact pricing algorithm runs in subexponential time. this is the first exact lattice algorithm to break the exponential-time barrier. because this lattice converges to the continuous-time stock price process, the proposed algorithm is guaranteed to converge to the desired continuous-time option value.
quantum algorithms for some hidden shift problems. almost all of the most successful quantum algorithms discovered to date exploit the ability of the fourier transform to recover subgroup structures of functions, especially periodicity. the fact that fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. in this paper, we present three examples of &ldquo;unknown shift&rdquo; problems that can be solved efficiently on a quantum computer using the quantum fourier transform. for one of these problems, the shifted legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. we also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. this framework provides a unified way of viewing the ability of the fourier transform to capture subgroup and shift structure.