| Publication Title: |
How Much of a Hypertree can be Captured by Windmills? |
| Publication Author: |
Liang, Percy |
| Additional Authors: |
Nati Srebro |
| LCS Document Number: |
MIT-LCS-TR-978 |
| Publication Date: |
1-3-2005 |
| LCS Group: |
Algorithms |
| Additional URL: |
|
| Abstract: |
| 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. |
| To obtain this publication: |
|
|
|
To purchase a printed copy of this publication please contact
MIT
Document Services.
|