waashk/dblp huggingface dataset:
estimating the sortedness of a data stream. the distance to monotonicity of a sequence is the minimum number of edit operations required to transform the sequence into an increasing order; this measure is complementary to the length of the longest increasing subsequence (lis). we address the question of estimating these quantities in the one-pass data stream model and present the first sub-linear space algorithms for both problems. we first present o(&radic;n)-space deterministic algorithms that approximate the distance to monotonicity and the lis to within a factor that is arbitrarily close to 1. we also show a lower bound of &omega;(n) on the space required by any randomized algorithm to compute the lis (or alternatively the distance from monotonicity) exactly, demonstrating that approximation is necessary for sub-linear space computation; this bound improves upon the existing lower bound of &omega;(&radic;n) [lnvz06]. our main result is a randomized algorithm that uses only o(log2 n) space and approximates the distance to monotonicity to within a factor that is arbitrarily close to 4. in contrast, we believe that any significant reduction in the space complexity for approximating the length of the lis is considerably hard. we conjecture that any deterministic (1 + &epsilon;) approximation algorithm for lis requires &omega; (&radic;n) space, and as a step towards this conjecture, prove a space lower bound of &omega;(&radic;n) for a restricted yet natural class of deterministic algorithms.
finding a heaviest triangle is not harder than matrix multiplication. we show that for any &epsilon; > 0, a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time o(n&omega; + n2+&epsilon;), where &omega; is the exponent of fastest matrix multiplication algorithm. by the currently best bound on &omega;, the running time of our algorithm is o(n2.376). our algorithm substantially improves the previous time-bounds for this problem recently established by vassilevska et al. (stoc 2006, o(n2.688)) and (icalp 2006, o(n2.575)). its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximum-weight one) in a graph. by applying or extending our algorithm, we can also improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph established in the papers by vassilevska et al. for example, we can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time o(m1.41).
fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree. computational inference of haplotypes from genotypes has attracted a great deal of attention in the computational biology community recently, partially driven by the international hapmap project. in this paper, we study the question of how to efficiently infer haplotypes from genotypes of individuals related by a pedigree, assuming that the hereditary process was free of mutations (i.e. the mendelian law of inheritance) and recombinants. the problem has recently been formulated as a system of linear equations over the finite field of f(2) and solved in o(m3n3) time by using standard gaussian elimination, where m is the number of loci (or markers) in a genotype and n the number of individuals in the pedigree. we give a much faster algorithm with running time o(mn2 + n3 log2 n log log n). the key ingredients of our construction are (i) a new system of linear equations based on some spanning tree of the pedigree graph and (ii) an efficient method for eliminating redundant equations in a system of o(mn) linear equations over o(n) variables. although such a fast elimination method is not known for general systems of linear equations, we take advantage of the underlying pedigree graph structure and recent progress on low-stretch spanning trees.
minimizing movement. we give approximation algorithms and inapproximability results for a class of movement problems. in general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or firefighter team to map labels or network messages) to achieve a global property of the network while minimizing the maximum or average movement. in particular, we consider the goals of achieving connectivity (undirected and directed), achieving connectivity between a given pair of vertices, achieving independence (a dispersion problem), and achieving a perfect matching (with applications to multicasting). this general family of movement problems encompasses an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability. in some cases, we obtain tight approximation and inapproximability results using direct techniques (without use of pcp), assuming just that p &ne; np.
improved algorithms for path, matching, and packing problems. improved randomized and deterministic algorithms are presented for path, matching, and packing problems. our randomized algorithms are based on the divide-and-conquer technique, and improve previous best algorithms for these problems. for example, for the k-path problem, our randomized algorithm runs in time o(4kk3.42m) and space o(nklogk + m), improving the previous best randomized algorithm for the problem that runs in time o(5.44kkm) and space o(2kkn + m). to achieve improved deterministic algorithms, we study a number of previously proposed de-randomization schemes, and also develop a new derandomization scheme. these studies result in a number of deterministic algorithms: one of time o(4k+o(k)m) for the k-path problem, one of time o(2.803kk nlog2 n) for the 3-d matching problem, and one of time o(43k+o(k)n) for the 3-set packing problem. all these significantly improve previous best algorithms for the problems.
scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes. communicating over a noisy channel is typically much easier when errors are drawn from a fixed, known distribution than when they are chosen adversarially. this paper looks at how one can use schemes designed for random errors in an adversarial context, at the cost of few additional random bits and without relying on unproven computational assumptions. the basic approach is to permute the positions of a bit string using a permutation drawn from a t-wise independent family, where t = o(n). this leads to several new results: &bull; we show that concatenated codes can correct errors up to the shannon capacity even when the errors are only slightly random --- it is sufficient that they be t-wise independently distributed, for t roughly &omega;(log n). &bull; we construct computationally efficient information reconciliation protocols correcting pn adversarial binary hamming errors with optimal communication complexity and entropy loss n(h(p) + o(1)) bits, where n is the length of the strings and h() is the binary entropy function. information reconciliation protocols allow cooperating parties to correct errors in a shared string. they are important tools in two applications: first, for dealing with noisy secrets in cryptography; second, for synchronizing remote copies of large files. entropy loss measures how much information is leaked to an eavesdropper listening in on the protocol. &bull; we improve the randomness complexity (key length) of efficiently decodable capacity-approaching private codes from &theta;(n log n) to n + o(n). we also present a simplified proof of an existential result on private codes due to langberg (focs '04).
restricted strip covering and the sensor cover problem. suppose we are given a set of objects that cover a region and a duration associated with each object. viewing the objects as jobs, can we schedule their beginning times to maximize the length of time that the original region remains covered? we call this problem the sensor cover problem. it arises in the context of covering a region with sensors. for example, suppose you wish to monitor activity along a fence (interval) by sensors placed at various fixed locations. each sensor has a range (also an interval) and limited battery life. the problem is then to schedule when to turn on the sensors so that the fence is fully monitored for as long as possible. this one-dimensional problem involves intervals on the real line. associating a duration to each yields a set of rectangles in space and time, each specified by a pair of fixed horizontal endpoints and a height. the objective is to assign a bottom position to each rectangle (by moving them up or down) so as to maximize the height at which the spanning interval is fully covered. we call this one-dimensional problem restricted strip covering. if we replace the covering constraint by a packing constraint (rectangles may not overlap, and the goal is to minimize the highest point covered), then the problem becomes identical to dynamic storage allocation, a well-studied scheduling problem, which is in turn a restricted case of the well known problem strip packing. we present a collection of algorithms for restricted strip covering. we show that the problem is np-hard and present an o(log log log n)-approximation algorithm. we also present better approximation or exact algorithms for some special cases, including when all intervals have equal width. for the general sensor cover problem, we distinguish between cases in which elements have uniform or variable durations. the results depend on the structure of the region to be covered: we give a polynomial-time, exact algorithm for the uniform-duration case of restricted strip covering but prove that the uniform-duration case for higher-dimensional regions is np-hard. we give some more specific results for two-dimensional regions. finally, we consider regions that are arbitrary sets, and we present an o(log n)-approximation algorithm for the most general case.
semi-oblivious routing: lower bounds. we initiate the study of semi-oblivious routing, a relaxation of oblivious routing which is first introduced by r&auml;cke and led to many subsequent improvements and applications. in semi-oblivious routing like oblivious routing, the algorithm should select only a polynomial number of paths between the source and the sink of each commodity, but unlike oblivious routing, the flow from each source to its sink is not just a scalar multiple of the single-commodity flow; any amount of flow can be sent along each selected path. semi-oblivious routing has several applications in traffic engineering and vlsi routing. trivially, any competitive ratio &rho; for oblivious routing (includling the polylogarthimic ratio in undirected graphs obtained by r&auml;cke) also implies competitive ratio &rho; for semi-oblivious routing. in this paper, we focus on lower bounds. we rule out the possibility of o(1) competitive ratio for semi-oblivious routing in undirected graphs by providing a lower bound of &omega;(log n/log log n) in grids or even series-parallel graphs. more strongly in directed graphs, we rule out the possibility of sub-polynomial competitive ratio when the number of paths between each source and its sink is in o(n1/5). the proof of our lower bound on the grid uses a non-markovian random walk on the integers with a mixing property which may be of independent interest. last but not least, our lower bounds on the grid can be significantly strengthened to show that with paths of at most b bends, the competitive ratio is in &omega;(n1/2b+1). this answers negatively a long-standing open problem on b-bend routing schemes in grids posed e.g. in [10, 6].
planar graphs are in 1-string. we prove that every planar graph is the intersection graph of strings in the plane, such that any two strings intersect at most once.
approximation algorithms for embedding general metrics into trees. we consider the problem of embedding general metrics into trees. we give the first non-trivial approximation algorithm for minimizing the multiplicative distortion. our algorithm produces an embedding with distortion (c log n)o(&radic;log &delta;), where c is the optimal distortion, and &delta; is the spread of the metric (i.e. the ratio of the diameter over the minimum distance). we give an improved o(1)-approximation algorithm for the case where the input is the shortest path metric over an unweighted graph. moreover, we show that by composing our approximation algorithm for embedding general metrics into trees, with the approximation algorithm of [bcis05] for embedding trees into the line, we obtain an improved approximation algorithm for embedding general metrics into the line. we also provide almost tight bounds for the relation between embedding into trees and embedding into spanning subtrees. we show that for any unweighted graph g, the ratio of the distortion required to embed g into a spanning subtree, over the distortion of an optimal tree embedding of g, is at most o(log n). we complement this bound by exhibiting a family of graphs for which the ratio is &omega;(log n/log log n).
linear programming relaxations of maxcut. it is well-known that the integrality gap of the usual linear programming relaxation for maxcut is 2 - &epsilon;. for general graphs, we prove that for any &epsilon; and any fixed bound k, adding linear constraints of support bounded by k does not reduce the gap below 2 - &epsilon;. we generalize this to prove that for any &epsilon; and any fixed bound k, strengthening the usual linear programming relaxation by doing &kappa; rounds of sherali-adams lift-and-project does not reduce the gap below 2 - &epsilon;. on the other hand, we prove that for dense graphs, this gap drops to 1 + &epsilon; after adding all linear constraints of support bounded by some constant depending on &epsilon;.
matrix scaling by network flow. a given nonnegative n x n matrix a = (aij) is to be scaled, by multiplying its rows and columns by unknown positive multipliers &lambda;i and &mu;j, such that the resulting matrix (aij&lambda;i&mu;j) has specified row and column sums ri and sj. we give an algorithm that achieves the desired row and column sums with a maximum absolute error &epsilon; in o(n4(log n + log h/&epsilon;)) steps, where h is the overall total of the result matrix. our algorithm is a scaling algorithm. it solves a sequence of more and more refined discretizations. the discretizations are minimum-cost network flow problems with convex piecewise linear costs. these discretizations are interesting in their own right because they arise in proportional elections.
buying cheap is expensive: hardness of non-parametric multi-product pricing. we investigate non-parametric unit-demand pricing problems, in which we want to find revenue maximizing prices for products p based on a set of consumer profiles c. a consumer profile consists of a number of non-zero budgets for different products and possibly an additional product ranking. once prices are fixed, each consumer chooses to buy one of the products she can afford based on some predefined selection rule. we distinguish between the min-buying, max-buying, and rank-buying models. for the min-buying model we show that it is not approximable within o(log&epsilon; |c|) for some constant &epsilon; > 0, unless np &sube; dtime(no(loglogn(), thereby closing the gap between the known algorithmic results and previous lower bounds. we also prove inapproximability within o(&ell;&epsilon;), &ell; being an upper bound on the number of non-zero budgets per consumer, and o(|p|epsi;) under slightly stronger assumptions and provide matching upper bounds. surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. for the max-buying model a ptas exists if a price ladder is given. we give a matching lower bound by proving strong np-hardness. assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. finally, we discuss implications for the rank-buying model.
succinct indexes for strings, binary relations and multi-labeled trees. we define and design succinct indexes for several abstract data types (adts). the concept is to design auxiliary data structures that occupy asymptotically less space than the information-theoretic lower bound on the space required to encode the given data, and support an extended set of operations using the basic operators defined in the adt. as opposed to succinct (integrated data/index) encodings, the main advantage of succinct indexes is that we make assumptions only on the adt through which the main data is accessed, rather than the way in which the data is encoded. this allows more freedom in the encoding of the main data. in this paper, we present succinct indexes for various data types, namely strings, binary relations and multi-labeled trees. given the support for the interface of the adts of these data types, we can support various useful operations efficiently by constructing succinct indexes for them. when the operators in the adts are supported in constant time, our results are comparable to previous results, while allowing more flexibility in the encoding of the given data. using our techniques, we design a succinct encoding that represents a string of length n over an alphabet of size &sigma; using nhk + o(n lg &sigma;) bits1 to support access/rank/select operations in o((lg lg &sigma;)3) time. we also design a succinct text index using nhk + o(n lg &sigma;) bits that supports pattern matching queries in o(m lg lg &sigma; + occ lg1+&epsilon; nlg lg &sigma;) time, for a given pattern of length m. previous results on these two problems either have a lg &sigma; factor instead of lg lg &sigma; in terms of running time, or are not compressible.
a linear work, o(n) time, parallel algorithm for solving planar laplacians. we present a linear work parallel iterative algorithm for solving linear systems involving laplacians of planar graphs. in particular, if ax = b, where a is the laplacian of any planar graph with n nodes, the algorithm produces a vector x such that ||x--x||a &le; &epsilon;, in o(n1/6+clog(1/&epsilon;)) parallel time, doing o(nlog(1/&epsilon;)) work, where c is any positive constant. one of the key ingredients of the solver, is an o(nklog2k) work, o(klogn) time, parallel algorithm for decomposing any embedded planar graph into components of size o(k) that are delimited by o(n/&radic;k) boundary edges. the result also applies to symmetric diagonally dominant matrices of planar structure.
making deterministic signatures quickly. we present a new technique of universe reduction. primary applications are the dictionary problem and the predecessor problem. we give several new results on static dictionaries in different computational models: the word ram, the practical ram, and the cache-oblivious model. all algorithms and data structures are deterministic and use linear space. representative results are: a dictionary with a lookup time of o(log log n) and construction time of o(n) on sorted input on a word ram, and a static predecessor structure for variable- and unbounded length binary strings that in the cache-oblivious model has a query performance of o(&verbar;s&verbar;/b + log &verbar;s&verbar;) i/os, for query argument s.
optimization problems in multiple-interval graphs. multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. we initiate the study of optimization problems in multiple-interval graphs by considering three classical problems: minimum vertex cover, minimum dominating set, and maximum clique. we describe applications for each one of these problems, and then proceed to discuss approximation algorithms for them. our results can be summarized as follows: let t be the number of intervals associated with each vertex in a given multiple-interval graph. for minimum vertex cover, we give a (2&minus;1/t)-approximation algorithm which also works when a t-interval representation of our given graph is absent. following this, we give a t2-approximation algorithm for minimum dominating set which adapts well to more general variants of the problem. we then proceed to prove that maximum clique is np-hard already for 3-interval graphs, and provide a (t2&minus;t+1)/2-approximation algorithm for general values of t &geq; 2, using bounds proven for the so-called transversal number of t-interval families.
approximation algorithms for prize collecting forest problems with submodular penalty functions. in this paper, we study the prize-collecting version of constrained forest problems with an arbitrary 0-1 connectivity requirement function and a submodular penalty function. our framework generalizes the prize collecting generalized steiner tree framework of hajiaghayi and jain [hj06] to incorporate more general connectivity requirements and penalty functions. we generalize their primal-dual algorithm using submodular function minimization to give a 3-approximation algorithm, and devise an lp rounding algorithm with a performance guarantee of 2.54.
combinatorial algorithms for web search engines: three success stories. how much can smart combinatorial algorithms improve web search engines? to address this question we will describe three algorithms that have had a positive impact on web search engines: the pagerank algorithm, algorithms for finding near-duplicate web pages, and algorithms for index server loadbalancing.
distributed algorithms for multicommodity flow problems via approximate steepest descent framework. we consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. we show first distributed solutions that allow 1 + &epsilon; approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.
pagerank and the random surfer model. in recent years there has been considerable interest in analyzing random graph models for the web. we consider two such models - the random surfer model, introduced by blum et al. [7], and the pagerank-based selection model, proposed by pandurangan et al. [18]. it has been observed that search engines influence the growth of the web. the pagerank-based selection model tries to capture the effect that these search engines have on the growth of the web by adding new links according to pagerank. the pagerank algorithm is used in the google search engine [1] for ranking search results. we show the equivalence of the two random graph models and carry out the analysis in the random surfer model, since it is easier to work with. we analyze the expected in-degree of vertices and show that it follows a powerlaw. we also analyze the expected pagerank of vertices and show that it follows the same powerlaw as the expected degree. we show that in both models the expected degree and the pagerank of the first vertex, the root of the graph, follow the same powerlaw. however, the power undergoes a phase-transition as we vary the parameter of the model. this peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.