Local Search (part 1)
Delve into the world of local search algorithms and explore the intricacies of Max Cut Partition challenges. Unravel the complexities of NP-hard problems, approximation guarantees, and the quest for optimal cut solutions. Witness the interplay between local and global optimization objectives in algorithmic decision-making.
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.
E N D
Presentation Transcript
Local Search (part 1) Haim Kaplan and Uri Zwick Algorithms in Action Tel Aviv University Last updated: April 2018 1
Max Cut Partition ? = (?,?)into 2 parts ?,? ? such that the number of edges ?,? ,? ?,? ? ? is maximized ? ? = ? ? 3
Few comments This problem is NP-hard, best approximation guarantee is 0.878, NP-hard to get more than 0.91 The analogous problem of finding a minimum cut is easier (how ?) 4
The idea Start with some cut and try to improve it by making local changes Stop when there is no local change that improves the cut 5
Local change ? ? 6
Local change ? ? 7
Local change ? ? 8
Local change ? ? 9
Local change ? ? 10
Local change ? ? 11
Local vs. global OPT When we stop we have a cut that we cannot improve by a local change (local opt) This need not be the largest cut (global opt) 12
Local OPT ? ? B A C D 13
Global OPT ? ? A B C D 14
Analysis There are two main parameters of interest: Time: How long it takes to get to a local optimum ? Quality of the local optimum ? 15
Quality of local opt ? = ? ? ? v Can this be the situation at a local optimum ? 16
Quality of local opt ? = ? ? ? v ? ? ? ?(?) ? ? = #edges incident to v that cross the cut ? ? = #edges incident to v that do not cross the cut 17
Quality of local opt ? = ? ? ? v ? ? ? ? ? ? ?,? ? ?? ?,? ? ? ?,? ? 2 ?,? 2 ?,? 18
Quality of local opt ? = ? ? ? v ? ? ? ? ? ? ?,? ? ?? ?,? ? ? ?,? ? ?,? ?,? ??? 2 |?| ? ?,? ? ?,? 2 19
Steps to local opt ?( ? ) Each step the size of the cut increases by at least one 20
Weighted graphs Partition ? = (?,?)into 2 parts ?,? ? such that the ? ?,? ,? ?,? ? ? is maximized ? ? = ? ? 21
Weighted graphs Works the same: Make a swap if it increases the weight of the cut ??? 2 ? ? ?,? ? 2 ? ?,? ? = ?(?,?) 22
Steps to local opt We construct a example with a long running time The example uses two kinds of vertices 36
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 37
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 38
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 39
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 ? ?4 > {? ?2,? ?3} > ? ?1 ?2 ?3 ? ? ?2 + ? ?3 > ? ?1 + ? ?4 ?1 ?4 40
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 ? ?4 > {? ?2,? ?3} > ? ?1 ?2 ?3 ? ? ?2 + ? ?3 > ? ?1 + ? ?4 ?1 ?4 41
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 ? ?4 > {? ?2,? ?3} > ? ?1 ?2 ?3 ? ? ?2 + ? ?3 > ? ?1 + ? ?4 ?1 ?4 42
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 ? ?4 > {? ?2,? ?3} > ? ?1 ?2 ?3 ? ? ?2 + ? ?3 > ? ?1 + ? ?4 ?1 ?4 43
Steps to local opt ?2 ? ?3 > ? ?1 + ? ?2 + ? ?4 ? ?3 ?1 ?4 ? ?4 > {? ?2,? ?3} > ? ?1 ?2 ?3 ? ? ?2 + ? ?3 > ? ?1 + ? ?4 ?1 ?4 44
Steps to local opt ?0 ?1 Moral: 2 flips of ?0caused 4 flips of ?1 60
Steps to local opt ?0 ?1 ?2 61
Steps to local opt ?0 ?1 ?2 62
Steps to local opt ?0 ?1 ?2 63
