Some applications of duality and flows : algorithms for network design and deterministic Markov decision processes
Abstract/Contents
- Abstract
- This thesis combines several algorithmic results from different domains unified by common themes in the techniques used---the strong use of linear programming duality and properties of vertex solutions and the use of network flows. First, we study the single-sink buy-at-bulk problem with an unknown cost function. We want to route flow through a graph from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing function f satisfying f(0)=0. Approximation algorithms are known for any given cost function, but we assume the function is not given. We describe a polynomial time algorithm that finds a small distribution over trees such that the expected cost of a tree for any f is within an O(1)-factor of the optimum cost for that f. We design a primal-dual algorithmic framework using the ellipsoid method that finds an O(1)-approximation if one exists, and then construct a separation oracle using a novel adaptation of the Guha, Meyerson, and Munagala [GMM 2001] algorithm for the single-sink buy-at-bulk problem that proves an O(1) approximation is possible for all f. We also present a simple, fast, combinatorial algorithm that constructs a single tree T such that for all f the cost f(T) is simultaneously a 47.45-approximation of the optimal cost for that particular f. This approaches the best approximation ratio currently achievable when the tree can be optimized for a specific function. Prior to this work, trees achieving simultaneous O(1)-approximations for all concave functions were previously not known to exist regardless of computation time. Second, we consider a problem arising in cloud computing where users can rent computing capability in the form of a network of virtual machines (VMs) with bandwidth guarantees between pairs of VMs. We study the problem of mapping such networks of VMs onto servers in the data center network so as to minimize network congestion. This problem differs from both traditional routing problems, in which the endpoints of communication demands are fixed, and most existing graph embedding work, in which the objective is to minimize some measure of stretch rather than congestion. We focus on a special case arising in practice in which the host network is a tree and the requests are paths. We prove that given a set of weighted path requests, we can embed a 1-epsilon fraction of requests with a congestion approximation of O(Hlog n/epsilon^2) if node capacities can be augmented by a 1+epsilon factor. If node capacities cannot be augmented, we prove we can embed a 1-epsilon fraction of requests with congestion at most poly(log n, log theta, epsilon^{-1}) where theta is the ratio of the maximum to minimum weights of the path requests. Our algorithm applies a randomized rounding scheme based on Group Steiner Tree rounding to a novel LP relaxation of the set of trees with a given number of leaves. Finally, motivated by the search for a strongly-polynomial algorithm for Markov decision processes (MDPs) and linear programming, we analyze the performance of the simplex method applied to deterministic MDPs. We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic MDPs regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n^3 m^2 log^2 n) iterations if the discount factor is uniform and O(n^5 m^3 log^2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1 [Ye 2011]. Unlike in the discounted case, the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of primal variables must lie and show that the simplex method always makes progress optimizing one layer, and when the upper layer is updated the algorithm makes a substantial amount of progress. In the case of nonuniform discounts, we define a polynomial number of ``milestone'' policies and we prove that, while the objective function may not improve substantially overall, the value of at least one dual variable is always making progress towards some milestone, and the algorithm will reach the next milestone in a polynomial number of steps.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Post, Ian Thomas |
|---|---|
| Associated with | Stanford University, Computer Science Department |
| Primary advisor | Goel, Ashish |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Trevisan, Luca |
| Thesis advisor | Ye, Yinyu |
| Advisor | Roughgarden, Tim |
| Advisor | Trevisan, Luca |
| Advisor | Ye, Yinyu |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Ian Post. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Ian Thomas Post
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...