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...

Full description

Bibliographic Details
Main Authors: Liang, Percy, Srebro, Nati
Other Authors: Algorithms
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