Samantha J. Riesenfeld

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-6

January 14, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.pdf

We study several instances of the following combinatorial optimization problem: Efficiently find a graph that satisfies, to the extent possible, a given set of constraints. The thesis begins with two NP-hard problems: The Minimum-Degree Minimum Spanning Tree (MDMST) problem is to find, given a graph, an MST of minimum degree. The Minimum Bounded-Degree Spanning Tree (MBDST) problem is to find, given a graph and an integer B, a minimum-cost tree in the set of spanning trees of degree at most B. We present the first polynomial-time constant-factor approximation algorithm for the MDMST problem, which uses the push-relabel framework developed by Goldberg [20] for the max-flow problem. It improves Fischer¿s local-search algorithm [14]. Via an analysis by Konemann and Ravi [34], our algorithm implies the first polynomialtime constant-factor bi-criteria approximation algorithm for the MBDST problem. It also works for a new generalization of the MDMST problem. Other results include the first true MBDST approximation algorithms: a polynomial-time algorithm incurring no error in cost, and a quasi-polynomial-time algorithm, based on augmenting paths, that significantly improves the error in degree by finding a spanning tree of optimal cost and degree B+O(log n log log n). Our cost-bounding method requires finding MSTs that meet both upper and lower degree bounds.

The second part of the thesis considers the problem of reconstructing a directed graph, given the vertices and an oracle for the reachability relation. We show this reduces to the problem of sorting a partially ordered set (poset). Sorting algorithms obtain information about a poset by queries that compare two elements. We give an algorithm that sorts a width-w poset of size n and has query complexity O(wn + n log n), meeting the information-theoretic lower bound. We describe a variant of Mergesort that has query complexity O(wnlogn), matching the upper bound shown by Faigle and Turan [13], and total complexity O(w^2 n log n). The exact total complexity of sorting remains unresolved. We also give upper and lower bounds for several related problems, including finding the minimal elements in a poset, which we show has query and total complexity Theta(wn), and its generalization, k-selection.

Advisors: Richard M. Karp

---

BibTeX citation:

@phdthesis{Riesenfeld:EECS-2008-6,
    Author= {Riesenfeld, Samantha J.},
    Title= {Optimization and Reconstruction over Graphs},
    School= {EECS Department, University of California, Berkeley},
    Year= {2008},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.html},
    Number= {UCB/EECS-2008-6},
    Abstract= {We study several instances of the following combinatorial optimization problem:  Efficiently find a graph that satisfies, to the extent possible, a given set of constraints.  The thesis begins with two NP-hard problems: The Minimum-Degree Minimum Spanning Tree (MDMST) problem is to find, given a graph, an MST of minimum degree. The Minimum Bounded-Degree Spanning Tree (MBDST) problem is to find, given a graph and an integer B, a minimum-cost tree in the set of spanning trees of degree at most B.  We present the first polynomial-time constant-factor approximation algorithm for the MDMST problem, which uses the push-relabel framework developed by Goldberg [20] for the max-flow problem. It improves Fischer¿s local-search algorithm [14].
Via an analysis by Konemann and Ravi [34], our algorithm implies the first polynomialtime constant-factor bi-criteria approximation algorithm for the MBDST problem. It also works for a new generalization of the MDMST problem.  Other results include the first true MBDST approximation algorithms: a polynomial-time algorithm incurring no error in cost, and a quasi-polynomial-time algorithm,
based on augmenting paths, that significantly improves the error in degree by finding a spanning tree of optimal cost and degree B+O(log n log log n). Our cost-bounding method
requires finding MSTs that meet both upper and lower degree bounds.

The second part of the thesis considers the problem of reconstructing a directed graph, given the vertices and an oracle for the reachability relation. We show this
reduces to the problem of sorting a partially ordered set (poset).  Sorting algorithms obtain information about a poset by queries that compare two elements. We give an algorithm that sorts a width-w poset of size n and has
query complexity O(wn + n log n), meeting the information-theoretic lower bound.  We describe a variant of Mergesort that has query complexity O(wnlogn), matching
the upper bound shown by Faigle and Turan [13], and total complexity O(w^2 n log n).  The exact total complexity of sorting remains unresolved.  We also give upper and lower bounds for several related problems, including finding
the minimal elements in a poset, which we show has query and total complexity Theta(wn), and its generalization, k-selection.},
}

EndNote citation:

%0 Thesis
%A Riesenfeld, Samantha J. 
%T Optimization and Reconstruction over Graphs
%I EECS Department, University of California, Berkeley
%D 2008
%8 January 14
%@ UCB/EECS-2008-6
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-6.html
%F Riesenfeld:EECS-2008-6