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 |