Approximation Algorithms for Bipartite Matching withMetric and Geometric CostsPankaj K. AgarwalR. SharathkumarDuke UniversityStanford UniversityABSTRACTKeywordsLet G G(A B, A B), with A B n, be a weightedbipartite graph, and let d(·, ·) be the cost function on theedges. Let w(M ) denote the weight of a matching in G, andM a minimum-cost perfect matching in G. We call a perfectmatching M c-approximate, for c 1, if w(M ) c · w(M ).We present three approximation algorithms for computingminimum-cost perfect matchings in G.First, we consider the case when d(·, ·) is a metric. For anyδ 0, we present an algorithm that, in O(n2 δ log n log2 (1/δ))time, computes a O(1/δ α )-approximate matching of G, whereα log3 2 0.631. Next, we assume the existence of adynamic data structure for answering approximate nearest neighbor (ANN) queries under d(·, ·). Given two parameters ε, δ (0, 1), we present an algorithm that, inO(ε 2 n1 δ τ (n, ε) log2 (n/ε) log(1/δ)) time, computes a O(1/δ α )approximate matching of G, where α 1 log2 (1 ε) andτ (n, ε) is the query and update time of an (ε/2)-ANN datastructure.Finally, we present an algorithm that works even if d(·, ·)is not a metric but admits an ANN data structure ford(·, ·). In particular, we present an algorithm that computes, in O(ε 1 n3/2 τ (n, ε) log4 (n/ε) log ) time, a (1 ε)approximate matching of A and B; here is the ratio ofthe largest to the smallest-cost edge in G, and τ (n, ε) is thequery and update time of an (ε/c)-ANN data structure forsome constant c 1.We show that our results lead to faster matching algorithmsfor many geometric settings.Matching, approximation algorithmsCategories and Subject DescriptorsF.2.2 [Theory of Computation]: Nonnumerical Algorithmsand Problems—geometrical problems and computations; G.2.2[Discrete Mathematics]: Graph Theory—graph algorithmsGeneral TermsAlgorithms, TheoryPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bearthis notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Requestpermissions from Permissions@acm.org.STOC’14, May 31– June 03, 2014, New York, New York, USA.Copyright 2014 ACM 978-1-4503-2710-7/14/05 . 15.00 UCTIONProblem Statement. Let G : G(A, B) G(A B, A B)be a bipartite graph with A B n, and let d : A B R 0 be the edge-cost function. Throughout this paper weassume that d(·, ·) can be evaluated in O(1) time. A perfectmatching M is a set of n vertex-disjoint edges in G(A, B).The cost Pof M , w(M ), is the sum of cost of its edges, i.e.,w(M ) (a,b) M d(a, b). When the cost function d(·, ·)is not obvious from the context, we will use the notationw(M, d) to represent the cost of M under d. The minimumcost bipartite matching (or optimal matching for brevity)is a perfect matching with the smallest cost; let M besuch a matching. A perfect matching M for G is calledc-approximate, for c 1, if w(M ) c · w(M ). In this paper,we develop approximation algorithms for computing optimalmatchings when A and B are points in a metric space, andwhen A and B are point sets in Rd and d(·, ·) is not necessarilya metric. The problem of computing an optimal matching inmetric and geometric settings arises in several applicationssuch as computer vision, shape analysis, computer graphics.For example, the problem in computer vision of trackingmultiple objects can be formulated as computing an optimalmatching between two sets of objects, and a metric is definedto measure the distance between a pair of objects [6].Previous work. Computing a maximum cardinality matching in a graph (both bipartite and general graphs) withn vertices and m edges takes O(m n) time [20, 23]. Thebound was improved for sparse graphs by Madry [22] (seealso [17, 28]). For weighted bipartite graphs, an optimalmatching with n vertices and m edges can be computed, inO(mn n2 log n) time, using the Hungarian algorithm [12].If the edge costs are positive integers bounded by nO(1) ,Gabow and Tarjan show that an optimal matching can becomputed in O(m n log n) time for bipartite graphs [14], and O(m n log3/2 n) time for general graphs [15]—almostmatching the time bounds for that of the unweighted case.There are algorithms that use algebraic methods to computeoptimal matching in matrix multiplication time [8, 27]. Bipartite matching is a special case of general graph matching,and the known algorithms for the latter are more complex.If A and B are points in a metric space, computing an optimal bipartite matching of A and B seems more challengingthan computing an optimal matching on a complete graph
of 2n points in the same metric space.1 For instance, an optimal matching in a set of 2n points in E2 , the 2D Euclideanplane, can be computed in O(n3/2 log5 n) time [33], while thebest known algorithm for computing an optimal matchingbetween two point sets of size n each in E2 takes O(n2 δ )time, for any constant δ 0 [1]. Recently, Sharathkumar [29]presented a O(n3/2 δ log(n ))-time algorithm to computean optimal matching between two point sets in E2 with positive integer coordinates bounded by . A sub-quadraticalgorithm for computing an optimal bipartite matching oftwo arbitrary point sets in E2 has remained elusive so far.The same trend holds for approximation algorithms. Several approximation algorithms are known for computing a(perfect) matching in a set of points (i.e., non-bipartite case)in arbitrary metric space [25, 26]. The best among those—a2-approximation algorithm by Goemans and Williamson [18]–runs in near-quadratic time [7, 13]. However, it does not extend to the bipartite setting. The only known near-quadratictime algorithm for the bipartite case computes a matching whose expected cost is within O(log n) of the optimalmatching [11].A near-linear time algorithm for computing a (1 ε)approximate matching in a set of n points in Ed , for d O(1),was first presented by Arora [4], and later improved byVaradarajan and Agarwal [34]. Following this, considerableeffort was made to design near-linear-time approximation algorithm for bipartite matching in low-dimensional Euclideanspaces [2, 21, 31, 34]. Only recently Sharathkumar and Agarwal [31] presented a near-linear time Monte-Carlo algorithmfor the bipartite case. The best-known deterministic approximation algorithm known for low-dimensional Euclideanspaces is by Varadarajan and Agarwal [34] that runs in timeO(n3/2 (log(n)/ε)O(d) ).In high-dimensional Euclidean space, when d is not assumed to be a constant, Goel et al. [16] presented an algorithm for computing a 2(1 ε)-approximate matching in a setof 2n points in Ed that runs in dO(1) n1 1/(1 ε) time, for anyconstant ε 0. For the bipartite case, besides the cubic-timeexact algorithm, the only known approximation algorithmsare an O(dn) time algorithm that computes an O(d log n)approximate matching [11], and an O(nd logO(1) n)-time algorithm that computes an O(log d log n)-approximate matching [3].A closely related problem is the maximum-cost matchingproblem — compute a matching with the maximum cost.While exact algorithms for maximum-cost matching andminimum-cost matching have the same running time, approximating minimum-cost matching is considerably harderthan approximating maximum-cost matching. For example,a simple greedy algorithm produces a 0.5-approximation tomaximum weight matching for any weighted graph. A similargreedy algorithm gives only an O(n0.58 ) approximation [26]even when the edge costs are assumed to satisfy triangleinequality. In fact, as observed by Avis [5], computing anO(n)-approximation of minimum-cost matching on a graphwith arbitrary edge costs takes the same time as computingthe maximum cardinalitymatching of a dense unweighted graph, i.e., Ω(m n) time. In contrast, Duan and Pettie [9]present an O(m/ε log(1/ε))-time algorithm to compute a(1 ε)-approximate maximum-cost matching.1Note that bipartite matching is not a special case of thenon-bipartite matching in this setting.Our results. We present three approximation algorithmsfor computing a minimum-cost matching in G. First, given aconstant δ (0, 1/3), we present, in Section 3, a deterministicalgorithm that computes, in O(n2 δ log n log2 1/δ) time, anO((1/δ)α )-approximate matching, where α log3 2 0.631,for the case when d(·, ·) is an arbitrary metric that can beevaluated in O(1) time. This is the first O(1)-approximationalgorithm that runs in o(n2.5 ) time. Moreover, our algorithmcomputes, in O(n2 logO(1) n) time, an O((log n/ log log n)α )approximate matching; this compares favorably to the randomized quadratic-time algorithm for computing a O(log n)approximate matching. Our algorithm is a variant of thescaling algorithms [14, 30]. Roughly speaking, our algorithmcomputes a partial matching at each scale, commits thismatching, and solves the problem recursively for unmatchedpoints at the next scale. We use the metric property of d(·, ·)to bound the cost of an optimal matching of the unmatchedpoints, and show that we compute an approximate matchingat each scale.In Section 4, we improve the above algorithm if d(·, ·)admits an efficient dynamic data structure for answeringε-approximate nearest-neighbor (ANN) queries. We presentan algorithm that given two parameters ε, δ (0, 1), computes an O(1/δ α )-approximate matching of A and B inO(ε 2 n1 δ τ (n, ε) log2 (n/ε) log(1/δ)) time. Here α 1 log2 (1 ε) and τ (n, ε) is the query and update time of theε/2-ANN data structure. Note that we sacrifice the approximation factor a little but gain substantially in the runningtime, provided τ (n, ε) is small. If we set ε 1/ log2 (1/δ),the algorithm computes a O(1/δ)-approximate matching.Finally, by combining the ideas of the second algorithmwith the Hungarian algorithm, we present an algorithm thatworks even when d(·, ·) is not necessarily a metric but admitsan efficient ANN data structure (e.g. squared Euclidean distance). More precisely, we present in Section 5 an algorithmthat computes a (1 ε)-approximate matching of A and B intime O(ε 1 n3/2 τ (n, ε) log4 (n/ε) log ); here is the ratioof the largest to the smallest-cost edge in G. Previously,data structures for answering (additive) weighted nearestneighbor (WNN) queries were used to speed up the Hungarian algorithm for geometric settings [30]. It is tempting toattain an approximation algorithm by replacing the WNNdata structure in these algorithms with the one that answersapproximate WNN queries, with the hope that the lattercan be answered more quickly. However, it is unlikely thatapproximate WNN queries can be answered quickly—in timesimilar to unweighted ANN queries, because exact NN queriescan be reduced to answering approximate WNN queries. Weovercome this difficulty by using a different approach thatallows us to use a weaker notion of approximate WNN querieswhich can be answered using ANN data structure.These results lead to faster matching algorithms for manygeometric settings. We just mention two of them here:(i) For A, B Ed , with d Ω(log n), and for a constantδ 0, an O(1/δ log2 (1/δ) )-approximate matching can be computed in O(n1 δ log n) time. This is the first sub-quadraticalgorithm for computing an O(1)-approximate matching ofhigh-dimensional point sets.(ii) For A, B Rd , with d O(1), and for a constantδ 0, we obtain a deterministic algorithm that computesan O( 1δ )-approximate matching of A and B in O(n1 δ log n)time. The previously best known deterministic algorithmcomputes a 1δ -approximate matching in O(n3/2 logO(d) n)
time [34] (using our second algorithm). Alternatively, wealso obtain a deterministic algorithm that computes a (1 ε)1approximate matching of A and B in O( εO(d)n3/2 log5 (n/ε))time (using our third algorithm), while the algorithm in [34]takes O(n3/2 (log(n)/ε)O(d) ) time.2.PRELIMINARIES (a, b) A B, (a, b) M.(1)It is well-known that any dual-feasible perfect matching isoptimal with respect to d (·, ·); see [24]. Introduced by Gabowand Tarjan [14], a 1-feasible matching is a matching M andset of dual weights y(·) such thaty(a) y(b) d (a, b) 1y(a) y(b) d (a, b) (a, b) A B, (a, b) M.(2)A 1-optimal matching is a perfect matching that is 1-feasible.The notion of 1-feasible matching will be used in Section 3.An edge (a, b) A B is called eligible ify(a) y(b) d (a, b)y(a) y(b) d (a, b) 1(a, b) M,(a, b) / M.(3)The subgraph of G induced by the set of eligible edges iscalled the eligible graph (with respect to M ).Relaxing the notion of feasible edges differently, a matchingM is called ε-relaxed if the dual weights satisfy the followingcondition:y(a) y(b) d(a, b) dεd(a, b)e,y(a) y(b) d(a, b)w(M ) (1 ε)w(M ).Proof. Since M is a perfect matching, from (5),we haveXXXw(M ) d(u, v) y(u) y(v) y(v).In this section, we present a few concepts that will be usefulfor our algorithms. Let A, B, G, and d(·, ·) be as definedearlier. Given a matching M on G(A, B), an alternatingpath (or cycle) is a simple path (resp. cycle) whose edgesare alternately in and not in M . A free vertex is a vertex ofA B that has not been matched, i.e., not incident on anyedge of M . An augmenting path P is an alternating pathbetween two free vertices. M can be augmented by one edgealong P , by setting M M P , where is the symmetricdifference, i.e., remove P M from M and add P \ M to M .We refer to this step as an augmentation step.An alternating tree is a tree rooted at a free vertex of Bin which every path to the leaf node is an alternating path.While describing our algorithms, sometimes it is useful to M , defined as follows: Everyview G as a directed graph Gedge (a, b) M with a A and b B, is directed froma to b, and every edge (a, b) 6 M is directed from b to a.The in-degree (resp. out-degree) of every vertex of B (resp.A) is at most 1. Any alternating path is a directed path in M . An alternating tree T rooted at a free vertex b B is aG M , in the sense that T has a directed pathdirected tree in Gfrom the root b to every vertex in T.Recall that Hungarian and many other algorithms assigndual weights to each vertex of G. Let d (·, ·) be a distancefunction. For a vertex v A B, let y(v) be its dual weight.A matching M and a set of dual weights are dual feasible ify(a) y(b) d (a, b)y(a) y(b) d (a, b)Lemma 2.1. Let M be a perfect (ε/2)-relaxed matchingof A and B, and let M be an optimal matching of them. Ifw(M ) 2n/ε, then (a, b) A B, (a, b) M.(4)(5)The following lemma shows the significance of ε-relaxedmatchings.(u,v) M(u,v) Mv A BEvery edge (a, b) M satisfies (4) and w(M , d) thereforemlεXXd(u, v)y(a) d(u, v) 2 a A B2n,ε(u,v) M (1 3.ε)w(M ) n (1 ε)w(M , d).2ALGORITHM FOR ARBITRARY METRIC SPACELet A, B be two point sets of size n each in a metric space,and let d(·, ·) be the underlying metric such that the distancebetween an two points of A B can be computed in O(1) time.We describe an approximation algorithm for computing anoptimal matching of A and B under d(·, ·). Our algorithm is avariant of the scaling algorithms for matching [14, 30]. Beforepresenting the algorithm, we breifly describe the main ideabehind it. This description, although somewhat incorrect,conveys the main intuition.Main idea. Suppose we fix a scale of the Gabow-Tarjanalgorithm [14]. At a fixed scale, their algorithm runs instages, each of which computes, in O(n2 ) time, a maximalset of vertex-disjoint augmenting paths, augments the matching along these paths, and updates the dual weights of thevertices. If we run their algorithm for nα stages, then it computes a matching M1 that matches, in O(n2 α ) time, all butO(n1 α ) points of A and B, and w(M1 ) 2w(M ), where M is the optimal matching of A, B. Next, we compute an optimal matching M2 of the free points of A and B, using the Hungarian algorithm, which takes O(n3(1 α) ) time, and returnM1 M2 as a matching of A, B. Using the fact that d(·, ·) is ametric, we can argue that w(M2 ) w(M1 ) w(M ) 3w(M ).By setting α 1/4, we obtain a 5-approximate matchingof A, B in O(n9/4 ) time. We can repeat this process oncemore, but this time use the O(n9/4 ) algorithm, instead ofHungarian algorithm, to compute M2 . We obtain a faster algorithm that returns an O(1)-approximate matching, thoughthe constant is now larger than 5. By iterating this processmultiple times, we can obtain a trade-off between the approximation factor and the running time. How we do thiscorrectly and obtain a good trade-off requires some care, asdescribed below.There are three main differences between our and traditional scaling algorithms [14, 30]: (i) We commit the edgescomputed in the matching computed in one scale, and thenext scale computes a matching of only unmatched points.(ii) We compute a partial matching at each scale. By choosing the number of steps for which we run the algorithm ateach scale, we keep both the running time and the cost of thematching under control. (iii) In successive scales, we scaledown the edge costs instead of scaling up, so that the cost
of the optimal matching of unmatched points is linear in thenumber of the points.Algorithm. We now describe the algorithm in detail. Wechoose a parameter δ (0, 1/3] and set ε 2 log1 1/δ . Let3ω 0 be a real value such that w(M )/2 ω w(M ). Fornow, we assume that we have such a value of ω at our disposal.At the end, we describe how to choose ω. The algorithmworks in phases. In the beginning of phase i, for i 0, wehave sets Ai A and Bi B of points and a matching Miof the points in A \ Ai and B \ Bi ; set Ai Bi ni . Fori 0, A0 A, B0 B, n0 n, and M0 . If ni n2/3 ,we compute an optimal matching of Ai and Bi using theHungarian algorithm, which takes O(n3i ) O(n2 ) time. So,assume ni n2/3 . In phase i, we set the distance functionto be di (·, ·), defined as follows:di (a, b) di 1 (a, b)2(1 ε)2 nϕi 12d(a, b) · nεω if i 0,(6) if i 0,where ϕi 3i δ.We compute a (possibly partial) matching Mi of Ai and Biunder di (·, ·) using the algorithm Phase-Match describedbelow. We set Mi 1 Mi Mi . If Mi is a perfect matchingbetween Ai and Bi , we stop and return Mi 1 . Otherwise,we set Ai 1 (resp. Bi 1 ) to be the set of free vertices of Ai(resp. Bi ) and move to phase i 1.We now describe the Phase-Match algorithm, which issimilar to Gabow and Tarjan’s [14] algorithm but with someadditional twists. We set κi 30nϕi . The procedure worksεin stages. In the beginning of each stage, we have a setFAFi Ai and Bi Bi of free vertices, dual weights y(v) foreach point in Ai Bi and a 1-feasible matching M computedFso far. Initially, AFi Ai , Bi Bi , and M , andy(v) 0 for all v Ai Bi . At the end of the stage, ifwe have computed a perfect matching of Ai , Bi or run theprocedure for κi stages, we stop and return M as Mi .Each stage of Phase-Match consists of the following threesteps:(i) Finding augmenting paths. Let E Ai Bi be theset of eligible edges. We compute, in O(n2i ) time, a maximalset P of vertex-disjoint augmenting paths in E, as describedin [14, 30].(ii) Augmentationstep. We augment M along P, i.e., setSM M ( P P P ). For each vertex b Bi that lies on apath in P, set y(b) y(b) 1, to ensure that M continuesto be 1-feasible after the augmentation step. This step takesO(ni ) time because the paths in P are vertex disjoint.(iii) Dual-adjustment step. Consider the directed subgraph Gi formed by E, the set of eligible edges, as definedin Section 2. Let
we develop approximation algorithms for computing optimal matchings when Aand Bare points in a metric space, and when Aand Bare point sets in Rdand d(;) is not necessarily a metric. The problem of computing an optimal matching in metric and geometric settings arises in several applications such as computer vision, shape analysis, computer graphics.
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
The Bipartite Rationing Problem Herve Moulin and Jay Sethuramany May 2011; Revised December 2011, September 2012 Abstract In the bipartite rationing problem, a set of agents share a single re-source available in di erent \types", each agent has a claim over only a subset of the resour
Instructor: Is l Dillig, CS311H: Discrete Mathematics Introduction to Graph Theory 11/34 Questions about Bipartite Graphs I Does there exist a complete graph that is also bipartite? I Consider a graph G with 5 nodes and 7 edges. Can G be bipartite? Instructor: Is l Dillig, CS311H: Discrete Mathemat
An approximation scheme for problem X is a family of (1 ε)-approximation algorithms Aε (respectively, (1 ε)-approximation algorithms Aε) for problem X over all 0 ε 1. A polynomial time approximation scheme (PTAS) for problem X is an approximation scheme whose time complexity is polynomial in the input size.
10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan
service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största
Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid
HINDI 1. Anubhuti Hindi Pathmala Pustika Part 3 Eduzon Pub. 2. Nirjhar Moti Sulekh Part 3 Rachna Sagar Pub. 3. New Way Hindi Vyakaran Part 3 Gurukul Pub. MATHS 1. Maths Wiz Book - 3 By S.K.Gupta and Anubhuti Gangal S.Chand Publications . Class : IV Subject Name of the Book with the name and address of the Publisher ENGLISH 1 Stepping Stone A skill based course book – 4 Headword Publishing Co .