Probabilistic methods in combinatorial and stochastic optimization

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.

Bibliographic Details
Main Author: Vondrák, Jan, 1974-
Other Authors: Michael X. Goemans.
Format: Thesis
Language:en_US
Published: Massachusetts Institute of Technology 2005
Subjects:
Online Access:http://hdl.handle.net/1721.1/28827
_version_ 1826202255634726912
author Vondrák, Jan, 1974-
author2 Michael X. Goemans.
author_facet Michael X. Goemans.
Vondrák, Jan, 1974-
author_sort Vondrák, Jan, 1974-
collection MIT
description Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.
first_indexed 2024-09-23T12:04:37Z
format Thesis
id mit-1721.1/28827
institution Massachusetts Institute of Technology
language en_US
last_indexed 2024-09-23T12:04:37Z
publishDate 2005
publisher Massachusetts Institute of Technology
record_format dspace
spelling mit-1721.1/288272019-04-10T21:27:09Z Probabilistic methods in combinatorial and stochastic optimization Vondrák, Jan, 1974- Michael X. Goemans. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. Includes bibliographical references (leaves 103-106). (cont.) Packing/Covering problems, we prove upper and lower bounds on the adaptivity gap depending on the dimension. We also design polynomial-time algorithms achieving near-optimal approximation guarantees with respect to the adaptive optimum. Finally, we prove complexity-theoretic results regarding optimal adaptive policies. These results are based on a connection between adaptive policies and Arthur-Merlin games which yields PSPACE-hardness results for numerous questions regarding adaptive policies. In this thesis we study a variety of combinatorial problems with inherent randomness. In the first part of the thesis, we study the possibility of covering the solutions of an optimization problem on random subgraphs. The motivation for this approach is a situation where an optimization problem needs to be solved repeatedly for random instances. Then we seek a pre-processing stage which would speed-up subsequent queries by finding a fixed sparse subgraph covering the solution for a random subgraph with high probability. The first problem that we investigate is the minimum spanning tree. Our essential result regarding this problem is that for every graph with edge weights, there is a set of O(n log n) edges which contains the minimum spanning tree of a random subgraph with high probability. More generally, we extend this result to matroids. Further, we consider optimization problems based on the shortest path metric and we find covering sets of size 0(n(̂1+2/c) log2̂ n) that approximate the shortest path metric of a random vertex-induced subgraph within a constant factor of c with high probability. In the second part, we turn to a model of stochastic optimization, where a solution is built sequentially by selecting a collection of "items". We distinguish between adaptive and non-adaptive strategies, where adaptivity means being able to perceive the precise characteristics of chosen items and use this knowledge in subsequent decisions. The benefit of adaptivity is our central concept which we investigate for a variety of specific problems. For the Stochastic Knapsack problem, we prove constant upper and lower bounds on the "adaptivity gap" between optimal adaptive and non-adaptive policies. For more general Stochastic by Jan Vondrák. Ph.D. 2005-09-27T18:33:51Z 2005-09-27T18:33:51Z 2005 2005 Thesis http://hdl.handle.net/1721.1/28827 60351888 en_US M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 106 leaves 6813828 bytes 6826289 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology
spellingShingle Mathematics.
Vondrák, Jan, 1974-
Probabilistic methods in combinatorial and stochastic optimization
title Probabilistic methods in combinatorial and stochastic optimization
title_full Probabilistic methods in combinatorial and stochastic optimization
title_fullStr Probabilistic methods in combinatorial and stochastic optimization
title_full_unstemmed Probabilistic methods in combinatorial and stochastic optimization
title_short Probabilistic methods in combinatorial and stochastic optimization
title_sort probabilistic methods in combinatorial and stochastic optimization
topic Mathematics.
url http://hdl.handle.net/1721.1/28827
work_keys_str_mv AT vondrakjan1974 probabilisticmethodsincombinatorialandstochasticoptimization