ECCC-Report TR05-029https://eccc.weizmann.ac.il/report/2005/029Comments and Revisions published for TR05-029en-usWed, 15 Jun 2005 00:00:00 +0300
Revision 1
| Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization |
Frank Neumann,
Marco Laumanns
https://eccc.weizmann.ac.il/report/2005/029#revision1We give faster approximation algorithms for the
generalization of two NP-hard spanning tree problems. First,
we investigate the problem of minimizing the degree of
minimum spanning forests. Fischer \cite{FISCH93}
has shown how to compute a minimum spanning tree of degree
at most $b \cdot \Delta^* + \lceil \log_b n \rceil$ in time
$O(n^{4 + 1/ \ln b})$ for any $b>1$, where $\Delta^*$ is the value of
an optimal solution. We model our generalization as a multi-objective optimization problem and give a deterministic algorithm that computes for each number of connected components a solution with the same
approximation quality as the algorithm of Fischer and runs
in time $O(n^{3 + 1/ \ln b})$. After that, we take a
multi-objective view on the problem of computing minimum
spanning trees with nonuniform degree bounds, which has been
examined by K{\"o}nemann and Ravi \cite{KOE03}. Given degree
bounds $B_v$ for each vertex $v \in V$, we construct an
algorithm that computes for each number of connected
components a spanning forest in which each vertex $v$ has
degree $O(B_v + \log n)$ and whose weight is at most a constant times the weight of a minimum spanning forest obeying the degree bounds. The total runtime of our algorithm is $O(n^{3 + 2 / \ln b})$ for an arbitrary constant $b>1$. Setting $b=e^k$, $k > 2/3$ an arbitrary constant, the runtime is by a factor $n^{3- 2/k} \log n$ less than the given bound by K{\"o}nemann and Ravi.
Wed, 15 Jun 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/029#revision1
Paper TR05-029
| Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization |
Frank Neumann,
Marco Laumanns
https://eccc.weizmann.ac.il/report/2005/029We give faster approximation algorithms for the
generalization of two NP-hard spanning tree problems. First,
we investigate the problem of minimizing the degree of
minimum spanning forests. The task is to compute for each
number of connected components a minimum spanning forest
whose degree is as small as possible. Fischer
has shown how to compute a minimum spanning tree of degree
at most $b \cdot \Delta^* + \lceil \log_b n \rceil$ in time
$O(n^{4 + 1/ \ln b})$ for any $b>1$, where $\Delta^*$ is the value of
an optimal solution. We model our
generalization as a multi-objective optimization problem and
give a deterministic algorithm that computes for each number
of connected components a solution with the same
approximation quality as the algorithm of Fischer and runs
in time $O(n^{3 + 1/ \ln b})$. After that, we take a
multi-objective view on the problem of computing minimum
spanning trees with nonuniform degree bounds, which has been
examined by K{\"o}nemann and Ravi. Given degree
bounds $B_v$ for each vertex $v \in V$, we construct an
algorithm that computes for each number of connected
components a spanning forest in which each vertex $v$ has
degree $O(B_v + \log n)$ and whose weight is at most a
constant times the weight of a minimum spanning forest
obeying the degree bounds. The total runtime of our
algorithm is $O(n^5)$, which is by a factor of $n \log n$
less than the algorithm of K{\"o}nemann and Ravi.
Mon, 07 Mar 2005 13:34:37 +0200https://eccc.weizmann.ac.il/report/2005/029