Analysis of Approximation Algorithms for Combinatorial Problems
In this study, heuristic algorithms for approximate solutions to polynomial complete optimization problems are examined, evaluating their worst-case behavior and performance compared to optimal solutions. Various combinatorial problems such as the knapsack problem, set covering problems, and finding the maximum clique in a graph are discussed in terms of algorithm efficiency and solution ratios.
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
Approximation Algorithms for Combinatorial Problems David S. Johnson Journal of Computer and System Sciences, Vol.9, pp.256-278 (1974) Presenter: Shiou-Zong Chiou Date:2016/11/08
Abstract Simple, polynomial-time, heuristic algorithms for finding approximate solutions to various polynomial complete optimization problems are analyzed with respect to their worst case behavior, measured by the ratio of the worst solution value that can be chosen by the algorithm to the optimal value. For certain problems, such as a simple form of the knapsack problem and an optimization problem based on satisfiability testing, there are algorithms for which this ratio is bounded by a constant, independent of the problem size, For a number of set covering problems, simple algorithms yield worst case ratios which can grow with the log of the problem size. And for the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as ??, where ? is the problem size and ? > 0 depends on the algorithm.
Subset-Sum ???????= {< ?,?,? >} ?????< ?,?,? > = {? ?: ? ? ?(?) ?} < ?,?,? > = ??? ? ? :? ? ??? ?(? ) ? ???? = ? ? ?(?) ?? 5 ?? 9 ?? 48 ?? 7 ?? 24 ?? 5 ?? 10 ?? 19 ?? 76 T s ? = 44 < ?,?,? > = {?1,?5,?6,?7}
Subset-Sum ? 1. Let ??? be that subset of {? ?:? ? > measure is closest to, without exceeding ?. Let ??? be this measure, and set ???? = ? ???. 2. If ? ????,? ? + ??? > ?, halt and return ???. 3. Let ? be an element of ???? for which ? ? + ??? is closest to, without exceeding, ?. 4. Set ???? = ???? {?}. ??? = ??? {?}, ??? = ??? + ?(?). 5. Go to 2. ?+1} whose
Subset-Sum ?? ?? ?? 5 5 5 ?? ?? ?? 9 9 9 ?? ?? ?? 48 48 48 ?? 7 7 7 ?? ?? ?? 24 24 24 ?? ?? ?? 5 5 5 ?? ?? ?? 10 10 10 ?? ?? ?? 19 19 19 ?? ?? ?? 76 76 76 ?? ?? T T T s s s ? = 44 ? = 44 ? = 44 ?1 1. ??? = {?5}, ??? = 24 2. ??? = {?5,?8}, ??? = 43
Subset-Sum T ?? ?? s 5 s 5 s 5 ?? ?? ?? ?? ?? ?? ?? 48 48 48 ?? ?? ?? 7 7 7 ?? ?? ?? 24 24 24 ?? ?? ?? 5 5 5 ?? ?? ?? 10 10 10 ?? ?? ?? 19 19 19 ?? 76 76 76 ?? ?? T T 9 9 9 ? = 44 ? = 77 ? = 44 ??? ?0 ??? ?1????? ???) ?(?0 ????? ?0= ?0 ?1= ?1 ?(?1 If ?1????? ?0 If some ? ?0 ???) ?????, ?1 would be optimal. ?????, and ? ?1?????, ? ? + ? ?1 > ? ? ?+1= ?? ?+1 ? ?+1< ?,?,? > ? ?1 > ? ? ? ? <?,?,?> ? ?1 ?+1 ?
Maximum Satisfiability ???????= {?:? is a finite set ?1,?2, ,?? of clauses } ?????? = {? ?:there exists a truth assignment ? which satisfies every clause ? ? } ???? = |? | ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3,?6 , ?2,?4,?5,?7,?8, ?1,?2 ? =
Maximum Satisfiability 1. Set ??? = , ???? = , ???? = ?, ??? = ? 2. If no literal in ??? is contained in any clause of ????, halt and return ???. 3. Let ? be the literal in ??? which is contained in the most clauses of ????, and ?? be the set of clauses in ???? which contain ?. 4. Set ??? = ??? ??,???? = ???? ??,???? = ???? ? ,??? = ??? {?,?} 5. Go to 2.
Maximum Satisfiability ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3,?6 , ?2,?4,?5,?7,?8, ?1,?2 ?1,?2 ?1,?2 ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3,?6 , ?2,?4,?5,?7,?8, ?2,?4,?5,?7,?8, ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3,?6 , ? = ? = ? =
Maximum Satisfiability ??? ? ???? ? ? = ??? + |????| ?+1 ? |???| ? |???| ?+1 ? ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3,?6 , ?2,?4,?5,?7,?8, ?1,?2 ? =
Maximum Satisfiability 1. Assign to each clause? ? a weight ? ? = 2 |?|. Set ??? = , ???? = , ???? = ?, ??? = ?. 2. If no literal in ??? is contained in any clause of ????, halt and return ???. 3. Let ? be any literal occurring in both ??? and a clause of ????. ?? be the set of clauses in ???? which contain ?, ?? be the set of clauses in ???? which contain ?. 4. If ? ???(?) ? ???(?), set??? = ??? ??,???? = ???? ??,???? = ???? ? , and for each ? ??, set ? ? = 2?(?). . 5. ??? = ??? {?,?}, and Go to 2.
Maximum Satisfiability Each ? ? 2 ?. Initially, the total weight of all the clauses in ???? cannot exceed |?| 2?. |????| |?| 2? ??? ? (1 2?) ? |???| 2? 1 ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3 , ?2,?4,?5,?7,?8, ?2,?4,?5,?7,?8, ?2,?4,?5,?7,?8, ?2,?4,?5,?7,?8, ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3 , ?2,?4,?5,?7,?8, ?2,?3, ?2,?3, ?2,?3, ?2,?3, ?2,?3, ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3 , ?2,?4,?5,?7,?8, ?2,?3, ?2,?3, ?2,?3 ?2,?3 ?2,?3 ?2,?3 ?2,?3 ?2,?3 ?2,?3 ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3 , ?2,?4,?5,?7,?8, ?2,?3, ?2,?3, ?2,?3, ?2,?3, ?2,?3, ?2,?3, ?2,?3, ?1,?2,?3, ?1,?3,?4,?5, ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?1,?5, ?1,?2,?3, ?1,?3,?4,?5, ?1,?5, ?2,?3 , ?2,?3 , ?2,?3 , 1 4 1 4 1 32 1 4 1 4 2 4 2 4 4 4 1 4 1 4 1 32 1 4 1 4 1 4 1 4 1 4 1 4 2 4 2 4 2 4 1 4 1 4 1 4 1 4 1 8 1 16 1 16 1 4 1 4 1 32 1 4 1 4 1 4 1 4 1 4 1 4 1 4 2 8 2 8 2 16 1 8 2 8 2 16 2 16 1 4 1 4 1 32 1 32 1 32 1 32 2 8 2 8 2 16 2 16 1 4 1 4 1 ? = ? = ? = ? = ? = ? = ? = 2? |?| |???|
Set Covering I ???????= {?:? is a finite family {?1,?2, ,??} of finite sets} ?????? = {? ?: ? ? ? = ? ??} ???? = |? |
Set Covering I 1. Set ??? = ,????? = ? ??,? = ? ,??? ? = ??,1 ? ?. 2. If ????? = , halt and return ???. 3. Choose ? ? such that ??? ? is maximized. 4. Set ??? = ??? ??,????? = ????? ??? ? ,??? ? = ??? ? ??? ? ,1 ? ?. 5. Go to 2.
Set Covering I 1 6 |?| ? ? ? ? ? ? ? ?(?) ? ?? ? 1 1 1 5 1 12 ? 1 4 ? ? 1 ? ?=1
Set Covering II ???????= {?:? is a finite family {?1,?2, ,??} of finite sets} ?????? = {? ?: ? ? ? = ? ??} ???? = |?|
Set Covering II 1. Set ??? = ,???? = ?,????? = ? ??. 2. If ????? = , halt and return ???. 3. Let ? ???? be that set ? which minimizes ?????(?) =|? ?????| |? ?????|. 4. Set ??? = ??? ? .????? = ????? ? , ???? = ???? {? }. 5. Go to 2.
Set Covering II 3 5 3 2 2 1 4 4 4 4 3 2 2 1
Set Covering II ? ?0 = ? ? ,1 ? ? ?? ? = ? ????? ,?? ?1 = ? ?1??(?) ? ?1 = ? + ?? ?1 ??(?1) ? ? ln ? + 1 1 ? ?1 ? ?0[ln ? + 1] ? ?1 ? ?0= ln ? + 1 X COVER Y Ratio(S )
Graph Coloring ???????= {? = ?,? :? is a finite undirected graph with nodes ? and edge ?}. ?????= {?:? 1,2, , ? : if there is an edge between nodes ? and ?, ?(?) ?(?)}. ???? = |?:? = ? ? , for some ? ?}|.
Graph Coloring 1. Set ????????? = ?,??????? ? = ,1 ? ? ,? = 1. 2. If ????????? = , halt and return ??????? ? ,1 ? ?. 3. If each node in ????????? is connected to some node in ???????[?], set ? = ? + 1. 4. Let ? be a node in ????????? with maximum degree among those not connected to any node in ???????[?]. 5. Set ??????? ? = ??????? ? ? . ????????? = ????????? ? , and go to 2.
Graph Coloring 4. Let ???? be that subset of ????????? made up of all the points not connected to any member of ???????[?]. Let ? be the node in ???? connected to the fewest other nodes in ????.
Graph Coloring 1. Set ????????? = ?,??????? ? = ,1 ? ? ,? = 1. 2. If ????????? = , halt and return ??????? ? ,1 ? ?. 3. Let ??? be the maximum sized independent subset of ?????????. 4. Set ??????? ? = ???. ????????? = ????????? ???, ? = ? + 1, and go to 2.
Maximum Clique ???????= {? = ?,? :? is a finite undirected graph with nodes ? and edge ?}. ?????? = {? ?: there is an edge in ? between each pair of nodes in ?}. ???? = |? |.
Maximum Clique 1. Set ??? = ,???? = ?. 2. If REST = , halt and return ???. 3. Let ? ???? be that element connected to the most other elements of ????. 4. Set ??? = ??? ? .???? = ???? {points not connected to ?}. 5. Go to 2.
Maximum Clique 1. Set ??? = ?. 2. If ??? is a clique, halt and return ???. 3. Let ? ??? be the node connected to the fewest other nodes in ???. 4. Set ??? = ??? {?} and go to 2.
