| Título: | Probabilistic methods in combinatorial and stochastic optimization |
| Autores: | Vondrák, Jan, 1974- |
| Fecha: |
2005-09-27 2005-09-27 2005 2005 |
| Publicador: | MIT |
| Fuente: |
 |
| Tipo: | Thesis |
| Tema: | Mathematics. |
| Descripción: |
(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. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. Includes bibliographical references (leaves 103-106). |
| Idioma: | Inglés |
1 Problem Investigation in High-Hazard Industries: Creating and Negotiational Learning por Hatakenaka, Sachi,Rudolph, Jenny,Carroll, John S. | 6 Trade Linkages and Output-Multiplier Effects: A Structural VAR por Forbes, Kristin J.,Abeysinghe, Tilak |
2 Global sourcing in the automotive supply chain:The case of Fiat Auto por Volpato, Giuseppe,Camuffo, Arnaldo | 7 Description Of Procedures In Automotive Engine Plants por Artzner, Denis,Whitney, Dr. Daniel |
3 Reading Courtesy Amounts on Handwritten Paper Checks por Palacios, Rafael,Wang, Patrick S.P.,Gupta, Amar | 8 Mobility Issues in the Developing World por Gakenheimer, Ralph |
4 On Trees and Logs por Pavlova, Anna,Cass, David | 9 Saturn, The GM/UAW Partnership por Rubinstein, Saul,Kochan, Thomas |
5 Academic Earmarks and the Returns to Lobbying por De Figueiredo, John M.,Silverman, Brian S. | 10 Toward a Stakeholder Theory of the Firm: The Case of the Saturn Partnership por Kochan, Thomas,Rubinstein, Saul |