Linear Programming (Optimization)

Linear Programming (Optimization)

3.3 Applications of Maximum Flow and Minimum Cut Bipartite Matchings and Covers A cover of an undirected graph is a set of nodes such that every edge of G has at least one end in . For any matching and any cover , each edge in has an end in and the corresponding nodes in C are all distinct. (primal-dual relation) Thm 3.14 (Knigs Theorem, 1931) : (Knig-Egervry Thm) For a bipartite graph G, max { : a matching} = min { : a cover} Combinatorial Optimization 2016 1 (Transform to max flow problem) P Q Q P a A a A b B b

B c C c C r d D d D f F f F h H h H

i I i I urp=1 s uqs=1 upq= Combinatorial Optimization 2016 2 (Maximum matching and corresponding flow) a A a A b B b B

c C c C r d D d D f F f F h H h H i I

i I urp=1 s uqs=1 upq= node cover Combinatorial Optimization 2016 3 (Identifying -incrementing paths) a A a A b B b B c C

c C r urp=1 d D f F h H i I upq= s uqs=1 r urp=1 d D

f F h H i I upq= s uqs=1 node reachable from Combinatorial Optimization 2016 4 (blue nodes defines cut = flow value) a A a A b B

b B c C c C r urp=1 d D f F h H i I upq= node reachable from Combinatorial Optimization 2016

s uqs=1 r urp=1 d D f F h H i I upq= s uqs=1 : cut arcs Note that no cut arc from blue in green in (O.w. cut capacity is ) 5 a

A a A b B b B c C c C r urp=1 d D f F h H

i I upq= Let {blue nodes} Combinatorial Optimization 2016 s uqs=1 r urp=1 d D f F h H i I s uqs=1

upq= Cover (pink) Capacity of cut 6 s r min cut: where no edge from to Cover Capacity of cut Running time: Combinatorial Optimization 2016 7 (Halls Theorem) Reference: Linear Programming, Vasek Chvatal, 1983, Freeman, p336-338. System of distinct representatives Given a set and a family of subsets of , a system of distinct representative (SDR) is a set of distinct elements of such that for . Halls Theorem: The family does not have an SDR if and only if there is a set such that . ---- (20.14) (The family has an SDR if and only if for every subset of we have .) Pf) later.

Combinatorial Optimization 2016 8 q1 S1 S2 S3 S4 S5 q2 q3 q4 q5 q6 q1 S1 S2 S3 S4 S5 q2 q3 q4 q5 q6 The family has an SDR iff the corresponding bipartite graph has a matching of size . Combinatorial Optimization 2016 9

q1 S1 q2 S2 q3 S3 q4 S4 q5 S5 q6 q1 S1 S2 S3 S4 S5 q2 q3 q4 q5 q6 Circled nodes have , hence no SDR.

Combinatorial Optimization 2016 10 Halls Theorem: The family does not have an SDR if and only if there is a set such that . ---(20.14) (The family has an SDR if and only if for every subset of we have .) Pf) ) clear. ) Suppose does not have an SDR. Corresponding bipartite graph has no matc hing of size . Let be the largest matching ( and be the smallest cover. By Kni gs thm . Let be such that iff the left node does not belong to . If , then each element , v iewed as a right node must be in . Otherwise would not be a cover. Hence is a subset of right nodes in . Since has precisely left nodes, it has right nodes. So (20.14) holds. Combinatorial Optimization 2016 11 Dilworths Theorem Chains and Antichains in Partially Ordered Sets (Reference: Linear Programming, Vasek Chvatal, 1983, Freeman, p338341.) A list of pairs satisfying the following conditions is called a partial order (i) no (ii) and together imply A set whose elements appear in a partial order is called a partially ordered set A subset of a partially ordered set is called a chain if or whenever and (The elements can be enumerated as in such a way that , , , ) A subset of a partially ordered set is called an antichain if for no . Combinatorial Optimization 2016 12

Dilworths Theorem: In every partially ordered set , the smallest number of chains whose union is equals the largest size of an antichain application: guided tour, airplane assignment pf) text exercise 3.37. We consider a different approach here. ex) Set , tours partial orders : ( need 3 guides, ) (Note that has no partial orders (antichain) ) Construct a bipartite graph by doubling each node as and . There exists an edge iff . Combinatorial Optimization 2016 13 a b a c b d c d e e g

f f A matching defines chains (guides) ex) (i) (ii) (iii) - In the matching, each tour has at most one successor and at most one predecessor. Otherwise, M would not be a matching. By concatenating successive tours, we obtain a set of chains (A chain may consists of a single tour) - Let be the number of chains and be the length (number of nodes) of -th chain. Then and which imply . (Hence min # of guides , : max matching) - Converse can be shown too, i.e. chains define sized matching . (Hence , i.e., min # of guides , : max matching) g Combinatorial Optimization 2016 14 Cover C* A* a b a c

b d c d e e g f f Different reasoning using Knigs Theorem: Let be a largest matching and be min cover. Define a set of trips as follows; trip iff and . No with is possible. (Otherwise, with , , hence not covered by , contradiction to being a cover.) no guide can take care of two different trips in . (e.g., ) need at least guides. But has at least elements (each node in makes only one trip ineligible for membership in ) Hence every schedule must use at least different guides. The schedule defined by , using only guides, is optimal. (from earlier) g

Combinatorial Optimization 2016 15 Proof of Dilworths Theorem: The partially ordered set may be thought of as a set of tours. Chains are those sets of tours that can be taken care of by one guide. The described procedure gives the smallest of chains. Along with the chains, the procedure also finds an antichain of size at least . Since every antichain shares at most one element with each of the chains , it must satisfy . So is a largest antichain and its size is (plug in for ). Combinatorial Optimization 2016 16 Optimal Closure in a Digraph Situation: If we want to choose project , then we must choose project also. We want to choose the set of projects which gives maximum profit Model as a problem on a digraph. Use directed arc if project precedes project . Find the maximum benefit set such that . (closure of ) (May be formulated as integer program using constraints , , .) Example: open pit mining problem. Partition the volume to be considered for excavation into small 3-dimensional blocks. Block produces profit of (profit of ore in cost of excavating ) If we need to excavate block to excavate block , we include arc in . Want to find a closed set in which maximizes profit. Combinatorial Optimization 2016 17 Convert to min-cut problem (max-flow problem) Divide the nodes into two sets and .

if and if . Construct . Add a source and a sink to the graph and add arc for each and arc for each . Capacity on the arcs are: for each and for each . The upper bounds on the original arcs are infinite. A set of nodes is closed if and only if the cut has finite capacity. If the capacity of is finite, then it equals Since is a constant, minimizing the capacity of amounts to maximizing . Combinatorial Optimization 2016 18 (Example) 2 -7 2 4 3 -1 2 7 4 3

-3 C 1 2 3 1 -1 Combinatorial Optimization 2016 19 Mengers Theorems Ref: Graph Theory with Applications, J. A. Bondy, U. S. R. Murty, 1976, 2008. Directed version: Lemma: Let be a digraph in which each arc has unit capacity. Then (a) The maximum flow is equal to the maximum number of arc disjoint directed -paths in ; and (b) The capacity of a minimum -cut is equal to the minimum number of arcs whose deletion destroys all directed -paths in G.

Thm: Let , be two nodes of a digraph . Then the maximum number of arcdisjoint directed -paths in G is equal to the minimum number of arcs whose deletion destroys all directed -paths in G. (pf) From above Lemma and max-flow and min-cut theorem. Combinatorial Optimization 2016 20 Thm: Let , be two nodes of a graph . Then the maximum number of edge-disj oint -paths in is equal to the minimum number of edges whose deletion destroy s all -paths in G. (pf) Replace each edge of G by two oppositely oriented arcs and apply the previ ous results. Combinatorial Optimization 2016 21 (node connectivity) Directed version: Thm: Let , be two nodes of a digraph , such that is not joined to . Then the maximum number of node-disjoint directed -paths in is equal to the minimum number of nodes whose deletion destroys all directed -paths in . (pf) Construct as follows ( except and ). Then directed -paths in are arcdisjoint if and only if the corresponding paths in are node-disjoint. Combinatorial Optimization 2016 1

22 Thm: Let and be two nonadjacent nodes of a graph . Then the maximum number of node-disjoint -paths in is equal to the minimum number of nodes whose deletion destroys all -paths. (pf) Replace each edge of G by two oppositely oriented arcs and use the previous transformation (reduction). Recall from connectivity results earlier. Thm 9.2: If has at least one pair has at least one pair of nonadjacent vertices, () = min {(,): ,, , }.( has at least one pair ) = min {(,): ,, , }.): ,): ,, , }., , }., ): ,, , }., ): ,, , }.}.}. Min cut can be obtained in polynomial time. Hence the (edge, node) connectivity of a graph can be found in polynomial time. Combinatorial Optimization 2016 23

Recently Viewed Presentations

  • Getting Ready for the PreACT Administrator Presentation Use

    Getting Ready for the PreACT Administrator Presentation Use

    Use of an approved word-to-word bilingual dictionary (containing no word definitions) Test instruction provided in the student's native language (including Spanish and a limited number of other languages initially) Testing in a non-distraction environment (i.e. in a separate room) You...
  • El Pretérito de los Verbos IR y SER Los Verbos Que Terminan ...

    El Pretérito de los Verbos IR y SER Los Verbos Que Terminan ...

    Preterite of IR and SER and -gar, -car, -zar Verbs Page 19 - Chp. 1 AVSR Realidades 3 Deportes y Acciones Correr Esquiar Jugar el futbol Montar en monopatin Nadar Navegar Patinar Ganar Jugar Participar Perder Practicar Run Ski Soccer...
  • Why Businesses Need to Digitally Transform? - Your

    Why Businesses Need to Digitally Transform? - Your

    These type of sensors also used in edge computing reduces the load on the communication system, the cost of automation system and can be implemented in very small to very large manufacturing units. Presently, these intelligent sensors are not easily...
  • World Geography EOC Review

    World Geography EOC Review

    World Geography EOC Review. ... Students will complete the religion chart and glue it on the back of the map. Students will use the symbols they created to label the major world religions on the map. Students will need to...
  • AIMS Review (Forces and Motion

    AIMS Review (Forces and Motion

    Take turns rolling the die and moving your game piece. If you land on a square with writing, do what it says. If you land on a square with a star, roll again IF the color matches your game piece....
  • The Widow at Windsor

    The Widow at Windsor

    'The Widow at Windsor' is a poem written by the writer Rudyard Kipling. It was published in 1892, and the widow refers to Queen Victoria. The poem illustrates how the Queen's soldiers strive to protect her kingdom.
  • ENGR 2 Engineering Design Graphics Tom Rebold AutoCAD

    ENGR 2 Engineering Design Graphics Tom Rebold AutoCAD

    Times New Roman Arial Calibri Default Design ENGR 2 Engineering Design Graphics AutoCAD on Campus Grading/Homework Lec 1: Getting Started (Ch1) 2D Construction (Ch2) Chapter 1 Toolbars Commands and Tools Starting a new drawing Starting a new drawing (cont) Slide...
  • 2.1 - Classification of skills Learning objectives To

    2.1 - Classification of skills Learning objectives To

    Simple skills have a limited amount of information to process. The skill has a smaller cognitive element. COMPLEX BASIC/SIMPLE Skill Classification - Basic/Simple & Complex Think. Pair. Share - Can you name other skills and where would they fit on...