The bottleneck distance is a natural measure of the distance between two finite point sets of equal cardinality. In this work, we consider the problem of indexing a set of @math planar point sets (of varying sizes) to create a database @math that supports nearest bottleneck distance queries: given a query point set @math of size @math , the point sets @math that are closest in terms of bottleneck distance are returned. Without loss of generality, we assume that all point sets belong to the unit box @math in the plane. The main contribution of this work is a trie -based data structure that is space efficient and supports @math -approximate nearest bottleneck queries in @math time, where @math is the minimum bottleneck distance from @math to any point set in @math . A direct consequence, of independent interest, is a simple @math time algorithm to @math -approximate @math , for any two point sets @math and @math . Finally, the querying algorithm proposed is easily adapted to support nearest subset and superset queries.
Bottleneck distance is closely related to the bipartite matching problem, which can be solved by the classic maximum flow technique of Hopcroft and Karp @cite_1 . The current best exact algorithm for planar bipartite matching is due to Efrat @cite_9 and runs in @math time for point sets of size @math .
@cite_9 @cite_1
2052551455 2157529519
In this paper, we study the non-bipartite maximum matching problem in the semi-streaming model. The maximum matching problem in the semi-streaming model has received a significant amount of attention lately. While the problem has been somewhat well solved for bipartite graphs, the known algorithms for non-bipartite graphs use @math passes or @math time to compute a @math approximation. In this paper we provide the first FPTAS (polynomial in @math ) for the problem which is efficient in both the running time and the number of passes. We also show that we can estimate the size of the matching in @math passes using slightly superlinear space. To achieve both results, we use the structural properties of the matching polytope such as the laminarity of the tight sets and total dual integrality. The algorithms are iterative, and are based on the fractional packing and covering framework. However the formulations herein require exponentially many variables or constraints. We use laminarity, metric embeddings and graph sparsification to reduce the space required by the algorithms in between and across the iterations. This is the first use of these ideas in the semi-streaming model to solve a combinatorial optimization problem. We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of @math , a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the @math bound.Our main result is a @math -approximation online algorithm for stochastic bipartite matching, breaking this @math barrier. Furthermore, we show that no online algorithm can produce a @math approximation for an arbitrarily small @math for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-) matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application. Given a large edge-weighted network @math with @math terminal vertices, we wish to compress it and store, using little memory, the value of the minimum cut (or equivalently, maximum flow) between every bipartition of terminals. One appealing methodology to implement a compression of @math is to construct a : a small network @math with the same @math terminals, in which the minimum cut value between every bipartition of terminals is the same as in @math . This notion was introduced by Hagerup, Katajainen, Nishimura, and Ragde [JCSS '98], who proved that such @math of size at most @math always exists. Obviously, by having access to the smaller network @math , certain computations involving cuts can be carried out much more efficiently. We provide several new bounds, which together narrow the previously known gap from doubly-exponential to only singly-exponential, both for planar and for general graphs. Our first and main result is that every @math -terminal planar network admits a mimicking network @math of size @math , which is moreover a minor of @math . On the other hand, some planar networks @math require @math . For general networks, we show that certain bipartite graphs only admit mimicking networks of size @math , and moreover, every data structure that stores the minimum cut value between all bipartitions of the terminals must use @math machine words. In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matching can be approximated in a single pass over the input using O(n) @math n @math 1-1 e @math O(n) @math 1-1 e @math O(n) @math 1-1 e @math O(n) @math 1-e^ -k k^ k-1 (k-1)!=1- 2 k +o(1 k) @math k$ passes in the vertex arrival model using linear space, improving upon previously best known convergence. A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In more detail, we obtain the following main results: Using iterative rounding for the first time in multi-objective optimization, we obtain multi-criteria PTASs (which slightly violate the budget constraints) for spanning tree, matroid basis, and bipartite matching with @math k = O ( 1 ) budget constraints. We present a simple mechanism to transform multi-criteria approximation schemes into pure approximation schemes for problems whose feasible solutions define an independence system. This gives improved algorithms for several problems. In particular, this mechanism can be applied to the above bipartite matching algorithm, hence obtaining a pure PTAS. We show that points in low-dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for @math k -budgeted matroid independent set. We present a deterministic approximation scheme for @math k -budgeted matching (in general graphs), where @math k = O ( 1 ) . Interestingly, to show that our procedure works, we rely on a non-constructive result by Stromquist and Woodall, which is based on the Ham Sandwich Theorem. We examine the classic on-line bipartite matching problem studied by Karp, Vazirani, and Vazirani [8] and provide a simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 -- 1 e. We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in U. When all the weights are equal, this reduces to the classic online bipartite matching problem for which Karp, Vazirani and Vazirani gave an optimal (1−1 e)-competitive algorithm in their seminal work [10]. Our main result is an optimal (1−1 e)-competitive randomized algorithm for general vertex weights. We use random perturbations of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in [10] in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of online budgeted allocations [14] in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of [14, 3] which apply when the bids are much smaller than the budgets. Let G=(U, V, E) be a bipartite graph with |U|=|V|=n. The factor size of G, f, is the maximum number of edge disjoint perfect matchings in G. We characterize the complexity of counting the number of perfect matchings in classes of graphs parameterized by factor size. We describe the simple algorithm, which is an approximation algorithm for the permanent that is a natural simplification of the algorithm suggested by Broder (1986) and analyzed by Jerrum and Sinclair (1988a, b). Compared to the algorithm by Jerrum and Sinclair (1988a, b), the simple algorithm achieves a polynomial speed up in the running time to compute the permanent. A combinatorial lemma is used to prove that the simple algorithm runs in time nO(n f). Thus: (1) for all constants α>0, the simple algorithm runs in polynomial time for graphs with factor size at least αn; (2) for some constant c, the simple algorithm is the fastest known approximation for graphs with factor size at least c log n. (Compare with the approximation algorithms described in Karmarkar (1988).) We prove the following complementary hardness results. For functions f such that 3⩽f(n)⩽n−3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For and e>0, for any function f such that 3⩽f(n)⩽n1−e, approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs. An announcement of these results appears in Dagum (1988). For the set of graphs with a given degree sequence, consisting of any number of @math and @math , and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of @math -matchings. We find the expected value of the number of @math -matchings of @math -regular bipartite graphs on @math vertices with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for @math -matchings in @math -regular bipartite graphs on @math vertices, and their asymptotic versions for infinite @math -regular bipartite graphs. We prove these conjectures for @math -regular bipartite graphs and for @math -matchings with @math . We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation @math , we show how to construct in @math time a data structure of size @math that answers distance queries in @math time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever @math . * We provide a linear-space exact distance oracle for planar graphs with query time @math for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space @math such that for any pair of nodes at distance D the query time is @math . Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with @math nodes, we can preprocess G in @math time to produce a data structure of size @math that can answer the following queries in @math time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For @math and space @math , we essentially improve the query time from @math to @math . Friedland's Lower Matching Conjecture asserts that if @math is a @math --regular bipartite graph on @math vertices, and @math denotes the number of matchings of size @math , then @math where @math . When @math , this conjecture reduces to a theorem of Schrijver which says that a @math --regular bipartite graph on @math vertices has at least @math perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely he proved that @math In this paper, we prove the Lower Matching Conjecture. In fact, we will prove a slightly stronger statement which gives an extra @math factor compared to the conjecture if @math is separated away from @math and @math , and is tight up to a constant factor if @math is separated away from @math . We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to @math --biregular bipartite graphs. There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity @math , the goal is to design an algorithm running in @math time for a parameter @math and a constant @math . In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in @math time or @math time, where @math is the tree-depth of the input graph. Because any graph of tree-width @math has tree-depth at most @math , our algorithms also run in @math time or @math time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by Network alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications - from biological networks to social networks to ontologies - where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting. The majority of the existing active methods focus on absolute queries ("are nodes @math and @math the same or not?"), whereas we argue that it is generally easier for a human expert to answer relative queries ("which node in the set @math is the most similar to node @math ?"). This paper introduces a novel relative-query strategy, TopMatchings, which can be applied on top of any network alignment method that constructs and solves a bipartite matching problem. Our method identifies the most informative nodes to query based on the top- @math matchings of a bipartite graph. We compare the proposed approach to several commonly-used query strategies and perform experiments on both synthetic and real-world datasets. Our matching-based strategy yields the highest overall performance, outperforming all the baseline methods by more than 15 percentage points in some cases. We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4 3log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms. Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1 epsilon) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to [Haeupler, Mirrokni and Zadimoghaddam WINE 2011] to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of [Jaillet and Lu Math. Oper. Res 2013] to 0.7299. We also consider two extensions, one is "known I.I.D." with non-integral arrival rate and stochastic rewards; the other is "known I.I.D." b-matching with non-integral arrival rate and stochastic rewards. We present a simple non-adaptive algorithm which works well simultaneously on the two extensions. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution f; however, these give us less control over the structure of f. We next remove all these additional constraints and randomly move from f to a feasible point on the matching polytope with all coordinates being from the set 0, 1 k, 2 k,..., 1 for a chosen integer k. The structure of this solution is inspired by [Jaillet and Lu Math. Oper. Res 2013] and is a tractable structure for algorithm design and analysis. The appropriate random move preserves many of the removed constraints (approximately [exactly] with high probability [in expectation]). This underlies some of our improvements, and, we hope, could be of independent interest. Let A and B be two sets of n objects in d , and let Match be a (one-to-one) matching between A and B . Let min(Match ), max(Match ), and Σ(Match) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of Match , respectively. Bottleneck matching— a matching that minimizes max(Match )— is suggested as a convenient way for measuring the resemblance between A and B . Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is roughly O(n 1.5 ) . For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n 1.5 log n ) . A semidynamic data structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Let @math be a @math -regular triangle-free graph with @math edges. We present an algorithm which finds a cut in @math with at least @math edges in expectation, improving upon Shearer's classic result. In particular, this implies that any @math -regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of @math . Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient randomised distributed (local) algorithm : each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using computational techniques . We show that for any fixed @math , there exists a weighted neighbourhood graph @math such that there is a one-to-one correspondence between heavy cuts of @math and randomised local algorithms that find large cuts in any @math -regular input graph. This turns out to be a useful tool for analysing the existence of cuts in @math -regular graphs: we can compute the optimal cut of @math to attain a lower bound on the maximum cut size of any @math -regular triangle-free graph. We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman and Steiner tree problems. Our technique produces approximation algorithms that run in @math time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of @math time compares favorably with the best strongly polynomial exact algorithms running in @math time for dense graphs. A similar result is obtained for the 2-matching problem and its variants. We also derive the first approximation algorithms for many NP-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [Math. Programming, 59 (1993), pp. 413--420]. We engineer an algorithm to solve the approximate dictionary matching problem. Given a list of words @math , maximum distance @math fixed at preprocessing time and a query word @math , we would like to retrieve all words from @math that can be transformed into @math with @math or less edit operations. We present data structures that support fault tolerant queries by generating an index. On top of that, we present a generalization of the method that eases memory consumption and preprocessing time significantly. At the same time, running times of queries are virtually unaffected. We are able to match in lists of hundreds of thousands of words and beyond within microseconds for reasonable distances. The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to @math .