How Much of a Hypertree can be Captured by Windmills?
Current approximation algorithms for maximum weight {\em hypertrees} find heavy {\em windmill farms}, and are based on the fact that a constant ratio (for constant width $k$) of the weight of a $k$-hypertree can be captured by a $k$-windmill farm. However, the exact worst case ratio is not known and...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30515 |
| _version_ | 1826213313470529536 |
|---|---|
| author | Liang, Percy Srebro, Nati |
| author2 | Algorithms |
| author_facet | Algorithms Liang, Percy Srebro, Nati |
| author_sort | Liang, Percy |
| collection | MIT |
| description | Current approximation algorithms for maximum weight {\em hypertrees} find heavy {\em windmill farms}, and are based on the fact that a constant ratio (for constant width $k$) of the weight of a $k$-hypertree can be captured by a $k$-windmill farm. However, the exact worst case ratio is not known and is only bounded to be between $1/(k+1)!$ and $1/(k+1)$. We investigate this worst case ratio by searching for weighted hypertrees that minimize the ratio of their weight that can be captured with a windmill farm. To do so, we use a novel approach in which a linear program is used to find ``bad'' inputs to a dynamic program. |
| first_indexed | 2024-09-23T15:47:04Z |
| id | mit-1721.1/30515 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:47:04Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305152019-04-12T08:37:39Z How Much of a Hypertree can be Captured by Windmills? Liang, Percy Srebro, Nati Algorithms Current approximation algorithms for maximum weight {\em hypertrees} find heavy {\em windmill farms}, and are based on the fact that a constant ratio (for constant width $k$) of the weight of a $k$-hypertree can be captured by a $k$-windmill farm. However, the exact worst case ratio is not known and is only bounded to be between $1/(k+1)!$ and $1/(k+1)$. We investigate this worst case ratio by searching for weighted hypertrees that minimize the ratio of their weight that can be captured with a windmill farm. To do so, we use a novel approach in which a linear program is used to find ``bad'' inputs to a dynamic program. 2005-12-22T02:20:23Z 2005-12-22T02:20:23Z 2005-01-03 MIT-CSAIL-TR-2005-002 MIT-LCS-TR-978 http://hdl.handle.net/1721.1/30515 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 12 p. 13845223 bytes 531507 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Liang, Percy Srebro, Nati How Much of a Hypertree can be Captured by Windmills? |
| title | How Much of a Hypertree can be Captured by Windmills? |
| title_full | How Much of a Hypertree can be Captured by Windmills? |
| title_fullStr | How Much of a Hypertree can be Captured by Windmills? |
| title_full_unstemmed | How Much of a Hypertree can be Captured by Windmills? |
| title_short | How Much of a Hypertree can be Captured by Windmills? |
| title_sort | how much of a hypertree can be captured by windmills |
| url | http://hdl.handle.net/1721.1/30515 |
| work_keys_str_mv | AT liangpercy howmuchofahypertreecanbecapturedbywindmills AT srebronati howmuchofahypertreecanbecapturedbywindmills |