Unraveling the Complexities of Beyond Steiner Tree Problem with DST-N and DGA: An Exploration

Dive into the intricacies of the Beyond Steiner Tree Problem and its solutions involving DST-N and DGA. Explore lower and upper bounds, add-only constraints, and various algorithms through a series of detailed images and descriptions. Delve deep into the world of optimization and beyond with Dean Oren's insights and visual aids.

• Steiner Tree Problem
• Optimization
• DST-N
• DGA
• Algorithm

robb_aya Follow

Uploaded on Sep 26, 2024 | 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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Beyond Steiner Tree Problem Beyond Steiner Tree Problem Dean Oren

4. DST-N (??,???) ?? ??

5. DST-N (??,??????) ?? ??

6. DST-N ? ?? ??? ?? =11 ? ? = ?,????,? = max 0<? ? 9 ??? = sup ? ? :max ?? = ? 6$ 6$ 9$ 9$ 5$ 5$

7. DST-R ??= #?? ?? 1 ?? 1 = 1 (??,??????) ?? ??

8. DST-N add-only: Lower Bound 1$/1$ (1) 0,0 1$ 0,1

9. DST-N add-only: Lower Bound 1.5$/1$ (2) 0,00 $ $ 1,01 0,01 $ $ 0,10

10. DST-N add-only: Lower Bound $ 2$/1$ (4) $ $ 0,000 $ 11,001 00,001 10,001 01,001 $ $ $ $ ? ??/??? ?? 1 + 1/2 log ?? 1 0,010 1,010 $ $ $ $ 01,011 00,011 10,011 11,011 $ $ $ 0,100 $

11. DST-N DGA ?0 1/3 $ 1/3 $ 1 $ ?1 ?4 5 $ 2 $ 2 $ ?2 ?3 1/3 $

12. DST-N DGA: Upper Bound 1 ? ?=2???? ?0,?? = 21 ?0 = max 3$ ?0 1/3 $ 1/3 $ 0 ?<1???? ?1,?? =1 ?1 = min 3$ 1 $ ?1 ?4 5 $ 2 $ 2 $ ?0 max 1 ? ? ?? ?2 ?3 1/3 $ 0 < ? ?. ?? ??? ?? < ?. ?? ???? ? ,?? 0 ?<2???? ?1,?? = 21 ?2 = min 3$

13. DST-N DGA: Upper Bound ?0 ? 1 ?0 max 1 ? ? ?? 2????????? ??? ?? 0 < ? ?. ?? ? 0 < ? ?. ?? ??? ?? < ?. ?? ???? ? ,??

14. DST-N DGA: Upper Bound ?? log? 1 2????????? = log? ??? ?? 1 ? ? ? 1 ?0 max 1 ? ? ?? 2????????? ??? ?? 0 < ? ?. ?? ? 0 < ? ?. ?? ??? ?? < ?. ?? ???? ? ,??

15. DST-N DGA ?0 1/3 $ 1/3 $ 1 $ ?1 ?4 5 $ 2 $ 2 $ ?2 ?3 1/3 $ ??? ?? ??? ?? 1 = ???? ??,?? 1 ??

16. DST-N DGA: Upper Bound ??? ?? ?? log? ??? ?? 1 ? ? ??? ?? ??? ?? 1 = ???? ??,?? 1 ?? ?? log? ??? ?? 1 ? ?

17. (M+1)$/1$ (2M+1) (M+1+?)$/(1+ ?)$ (2M+2) DST-N: Lower Bound (M+1)$/1$ (2M+3) ? = ?1,??? , ?2,??? , , ??+2,??? , ??+1,?????? , ??,?????? , , (?2,??????) ?1 1 $ 1 $ , ?1? ,??? ? $ ? $ ? $ , ?1? ,?????? ??+2=6 ?2 1 $ 1 $ ? $ ? $ ?5 ?3 ? $ ?4 ? ?? ??? ?? ? < ? ? + . ? 1 $ 1 $

18. Intermission

20. GSP Min Cost ?1 ?6 1$ 1$ 0.2$ 1$ 0.5$ ?2 ?5 ?1 ?2 ?3 1$ 1$ 0.2$ ?3 ?4 ?4 ?5 ?6

21. GSP Min Cost: ?-Nets ?6 ? = 1$ 1$ 0.2$ ?2 ?5 0.2$ ?3

22. GSP Min Cost: ?-Nets ? ? ? 2??

23. GSP Min Cost: Upper Bound ?6 ???? ?6,?3 = 1$ 1$ 0.2$ ???? ?5,?2 = 0.4$ ? =0.5$? = ?6,?5,?3,?2 = ?6,?3 ?2 ?5 0.2$ ?3