Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 149-153). / In this thesis, we study online optimization problems in routing and allocation applications. Online problems are problems where information is revealed incrementally, and decisions must be made before all information is available. We design and analyze algorithms for a variety of online problems, including traveling salesman problems with rejection options, generalized assignment problems, stochastic matching problems, and resource allocation problems. We use worst case competitive ratios to analyze the performance of proposed algorithms. We begin our study with online traveling salesman problems with rejection options where acceptance/rejection decisions are not required to be explicitly made. We propose an online algorithm in arbitrary metric spaces, and show that it is the best possible. We then consider problems where acceptance/rejection decisions must be made at the time when requests arrive. For dierent metric spaces, we propose dierent online algorithms, some of which are asymptotically optimal. We then consider generalized online assignment problems with budget constraints and resource constraints. We first prove that all online algorithms are arbitrarily bad for general cases. Then, under some assumptions, we propose, analyze, and empirically compare two online algorithms, a greedy algorithm and a primal dual algorithm. We study online stochastic matching problems. Instances with a fixed number of arrivals are studied first. A novel algorithm based on discretization is proposed and analyzed for unweighted problems. The same algorithm is modified to accommodate vertex-weighted cases. Finally, we consider cases where arrivals follow a Poisson Process. Finally, we consider online resource allocation problems. We first consider the problems with free but fixed inventory under certain assumptions, and present near optimal algorithms. We then relax some unrealistic assumptions. Finally, we generalize the technique to problems with flexible inventory with non-decreasing marginal costs. / by Xin Lu. / Ph.D.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/82724 |
| Date | January 2013 |
| Creators | Lu, Xin, Ph. D. Massachusetts Institute of Technology. Operations Research Center |
| Contributors | Patrick Jaillet., Massachusetts Institute of Technology. Operations Research Center., Massachusetts Institute of Technology. Operations Research Center. |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 153 pages, application/pdf |
| Rights | 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 |
Page generated in 0.0029 seconds