Games on Graphs

This presentation discusses the concept of Acyclic Unique Sink Orientations (AUSOs) on graphs, exploring their motivations, definitions, and algorithms for finding the sink. It also covers Linear Programming, focusing on maximizing linear objective functions subject to linear inequalities, exemplified by the Simplex Algorithm. Discover the relationship between AUSOs and Abstract Objective Functions (AOFs), as well as the sources and applications of AUSOs in cubes and linear programs.

• Graphs
• Linear Programming
• Acyclic Orientations
• Sink Orientations
• Algorithms

amor_jit Follow

Uploaded on Feb 15, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Games on Graphs Uri Zwick Tel Aviv University Lecture 7 Acyclic Unique Sink Orientations For the latest version of this presentation, see: http://www.cs.tau.ac.il/~zwick/GAMES-2019/Lecture-7- AUSO.pptx Last modified 20/01/2019

2. Lecture 7 (Acyclic) Unique Sink Orientations (of cubes) Motivation Definitions Where do AUSOs come from? Relation to Games. Algorithms for finding the sink

3. Linear Programming max ??? s.t. ?? ? Maximize a linear objective function subject to a set of linear inequalities (and equalities) Find the highest point in a polyhedron

4. The Simplex Algorithm [Dantzig (1947)] Start at some vertex. Move up, from vertex to vertex, along edges, until reaching the top.

5. Acyclic Unique Sink Orientations (AUSOs) Abstract objective functions (AOFs) Every face has a unique sink

6. (A)USOs of ?-cubes [ Stickney-Watson (1978) ] [ Williamson Hoke (1988) ] [ Szab -Welzl (2001) ] An (acyclic) orientation of the edges of the ?-cube such that every sub-cube has a unique sink. The ?-cube is the graph ??= (?,?), where ? = {0,1}?, and ? = ?,? ???,? = 1 }. Sink All edges are incoming

7. Sources of USOs and AUSOs Cube USOs: Linear Complementary Problems (LCP) Geometric problems such as smallest enclosing ball General Linear Programs (LP) Cube AUSOs: Linear Programs (LP) whose polytope is a cube (Non-degenerate) binary 1-player and 2-player games

8. (A)USOs of 1-cubes, 2-cubes

9. (A)USOs of 3-cubes USO Unique global sink but not AUSO not AUSO 19 non-isomorphic 3-USOs

10. (A)USOs of 5-cubes Slide taken from a presentation by Tibor Szab .

11. Finding the sink of an (A)USO An ?-AUSO has 2?vertices and ?2? 1edges. If it is given explicitly, we can find the sink in linear time . More interestingly: Suppose that the (A)USO is given via an oracle. We can query the oracle for the orientation of the edges at a given vertex. How many queries do we need, in the worst-case, to find the sink?

12. Formal definitions and notation An orientation ? of the ?-cube is a function ?: 0,1? 0,1? such that ? ?? ? ? ?? ? ? ? ?? ? ??= 1 ? ? ?? ?= 0 ? A sub-cube of ? is specified by ? 0,1, ?. ??= ? 0,1? ?? ??= ?? } Equivalently, a sub-cube is specified by (?,?), where ? 0,1? and ? = ? ??= }. Vertex ? is a sink of ? iff ? ? = 0?.

13. Flipping edges Lemma: If ? is a USO and ? ? = ? ? ??, for every ? 0,1?, then ? is also a USO. ? is obtained from ? by flipping the direction of all edges in the ?-th dimension. ? is not necessarily an AUSO even if ? is.

14. An orientation is an bijection Corollary 1: If ? is a USO, then ? ? ?(?), for every ? ?. Proof: Suppose that ? ? = ?(?). Flip edges repeatedly along appropriate dimensions until ? ? = ? ? = 0, a contradiction. Corollary 2: If ? is a USO, then every sub-cube has a unique source.

15. A product (blowup) construction outmap vertex ? ?: 0,1? 0,1? ??: 0,1? 0,1? ? 0,1? Take 2? copies of ?. Connect the 2? copies of ? by ??. ? = ? ?? ? ?,? = (? ? ,??(y)) ?: 0,1?+? 0,1?+? ?000 Lemma: If ? and ?? are (A)USOs, then ? = ? ?? is an (A)USO.

16. Hypersink replacement Slide by Tibor Szab .

17. Induced (A)USO Suppose that ?: 0,1? 0,1? is an ?-(A)USO. We want to define a ?-(A)USO ?? that represents ?. ??? = ? ?????? ? ? 1:? ??? ? ??? = ??? 0? ? , ? 0,1?. Lemma:?? is an (A)USO. (?? can be defined using any subset of ? coordinates.) Useful in obtaining recursive algorithms.

18. Decomposition algorithm Let ?(?) be the number of queries needed to find the sink of an ?-USO. ? ? ? ? ? ? ? Given an ?-USO ?, consider the induced ?-USO ??. ??? = ? ?????? ? ? 1:? Recursively run the algorithm on ??. To evaluate a vertex of ?? run the algorithm recursively on the corresponding ? ? -USO. In particular ? ? ? 2 ? ? 2 3?/2 1.73?.

19. Algorithm for 2-USOs Query an arbitrary vertex. If it is the sink, we are done. If it is not the source, follow to the unique path to the sink. If it is the source, jump to the antipodal vertex and follow to the unique path to the sink. ? 2 = 3 Note: We insist on evaluating the sink.

20. Fibonacci Seesaw [ Szab -Welzl (2001) ] Two sub-cubes ?1,?2 0,1, ? are antipodal, iff ?1 ? ?2 ? whenever ?1 ?, ?2 ? . Grow two antipodal ?-cubes whose sinks are known. When ? = ? 1 the sink of the whole cube is known. Start with an arbitrary pair of antipodal vertices.

21. Fibonacci Seesaw [ Szab -Welzl (2001) ] Two sub-cubes ?1,?2 0,1, ? are antipodal, iff ?1 ? ?2 ? whenever ?1 ?, ?2 ? . Let ?1,?2 be the sinks of ??1,??2. ? ?1 ? ?2 ? ? ?1 ? ? ?2 ? We extend the two ?-cubes along dimension ?. One of the sinks is also the sink of the ? + 1 -cube. We need to find the sink of the other ?-cube.

22. Fibonacci Seesaw [ Szab -Welzl (2001) ] ? ? = 2 + ? 0 + ? 1 + + ? ? 2 ? ? = ??+2 (Fibonacci numbers) ? ? 1.62?

23. Seven steps to Heaven [ Szab -Welzl (2001) ] ? 4 = 7 ? ? ? 4 ? ? 4 7?/4 1.63? Slightly worse than Fibonacci Seesaw. Can be combined with FS to yield ? ? 1.61? Best known deterministic algorithm for USOs and AUSOs!

24. Randomized algorithms for USOs ? 1 =3 2 ? 2 =43 20[ Szab -Welzl (2001) ] ? 3 =4074633 1369468 2.976[ Rote (2001) ] ? ? ? 3 ? ? 3 1.438? Best known randomized algorithm for USOs.

25. Finding the sink of an AUSO Can we use the acyclicity of AUSOs? Path-following algorithms? Improving algorithms? Natural algorithms: Arbitrary walk Random walk (Random-Edge) Random-Facet Switch-All Random-Jump

26. Klee-Minty cubes (1972) 011 111 001 ??? 1 101 010 110 ??? 1 000 100 ???has a Hamiltonian path (Gray code). Random-Edge on ???takes (?2), w.h.p. [Balogh-Pemantle (2007)]

27. Klee-Minty cubes (1972) Taken from a paper by G rtner-Henk-Ziegler

28. Random-Facet on the ?-cube [Ludwig (1995)] [G rtner (2002)] ?-th coordinate Start at some vertex ? of the ?-cube ?. Split the ?-cube into two (? 1)-cubes ?0 along a random coordinate ?. ?,?1 ? ? ? ? ? Recursively find the sink ? of the (? 1)-cube ?? ? containing ?. ? ? ?1 ?0 If ? is not the global sink, move to ? = ? e?. Recursively find the sink ? of the (? 1)-cube ?1 ? starting from ? . Exponential? Sub-exponential! The starting point ? of the second recursive call contains valuable information. ? containing ? ,

29. Switch-All on AUSO Start from an arbitrary vertex ? 0,1?. While ? is not the sink, move from ? to ? ? ? . Performs all improving switches simultaneously. One of the most natural sink finding algorithms. 2? ? steps. Switch-All performs only ? [ Mansour-Singh (1999) ] Switch-All performs 2 [ Schurr-Szab (2005) ] ? 2 steps. Conjecture/Speculation: ? ??+2???

30. Upper bound for Switch-All [ Mansour-Singh (1999) ] Let ?1,?2, ,?? be the vertices of ? visited by Switch-All. We say that ? ? iff there is a directed path from ? to ?. Claim: ?1 ?2 ?? In particular, by the acyclicity, ?1,?2, ,?? are distinct and ? 2?. Consider the subcube defined by ?? and its outgoing edges. ?? is the unique source of the subcube and ??+1 is in the subcube. The directed path from ?? to ??+1 is of length at least ? ?? , where ? ?? is the number of outgoing edges of ??. The paths from ?? to ??+1 are disjoint.

31. Upper bound for Switch-All [ Mansour-Singh (1999) ] ? >? ?? is of low-degree iff ? ?? As the outmap ?(?) is bijective, the number ?0 of low-degree vertices is at most 3, and high-degree if ? ?? 3. 1 3? 1.9?. ?/3 2? ? Thus, the length of the path from ?1 to ?? obtained by concatenating the paths from ?? to ??+1 is at least ? ?0 1 ? 3. ? 3 2? ? ?0 1 ? 32? 2? ? ?+ ?0+ 1 3 + ? 3 can be replaced by an upper bound of 2 + ? (The threshold ? 1 2 ? ?, for any ? > 0, yielding ? . Further such improvements are possible.) 2?

32. Lower bound for Switch-All [ Schurr-Szab (2005) ] Construct a product ? + 2 -AUSO ?. Take four copies of an ?-AUSO ?. 11 10 01 00 Where ??? is the number of steps taken by Switch-All starting from ?. Use a blue frame as ??, if ??? is odd, else green.

33. Lower bound for Switch-All [ Schurr-Szab (2005) ] Suppose that ???1 = ?, where ? is odd. Let ?1,?2, ,?? be the vertices of ? visited by Switch-All. Start Switch-All on ? from ?101. The sequence of vertices obtained is: ?101,?210,?301,?410, ,??10 ,??01,??00 In ?, the bottom copy of ? is a hypersink. Replace the bottom copy of ? by ? , to obtain ? , where ? ? = ? ? ?? ?0 On ? , Switch-All will perform ? 1 more steps from ??00. ?? ?101 = ? + 2 + ? 1 = 2? + 1 .

34. Lower bound for Switch-All [ Schurr-Szab (2005) ] Let ?(?) be the maximal number of steps performed by Switch-All on an ?-AUSO. We just proved that ? ? + 2 2? ? + 1. ? 2 = 3. (Please check.) By induction: ? 2? 2? 1. Hence, ? ? 2 ? 2 1, for ? even. Note: We count the number of evaluations, including the evaluation of the initial vertex.

35. AUSOs of the ?-cube Upper bound 1.8? Algorithm Lower bound RANDOM EDGE RANDOM FACET [Hansen-Z (2016)] 2 ? log ? 2 ? 2? ? [Hansen-Paterson-Z (2014)] [G rtner (2002)] [Matousek (1994)]

36. END of LECTURE 7