Network flow problems and congestion games : complexity and approximation results
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/35919 |
| _version_ | 1826190367100239872 |
|---|---|
| author | Meyers, Carol, Ph. D. Massachusetts Institute of Technology |
| author2 | Andreas S. Schulz. |
| author_facet | Andreas S. Schulz. Meyers, Carol, Ph. D. Massachusetts Institute of Technology |
| author_sort | Meyers, Carol, Ph. D. Massachusetts Institute of Technology |
| collection | MIT |
| description | This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. |
| first_indexed | 2024-09-23T08:39:11Z |
| format | Thesis |
| id | mit-1721.1/35919 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:39:11Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/359192019-04-09T18:59:34Z Network flow problems and congestion games : complexity and approximation results Meyers, Carol, Ph. D. Massachusetts Institute of Technology Andreas S. Schulz. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006. Includes bibliographical references (p. 155-164). (cont.) We first address the complexity of finding an optimal minimum cost solution to a congestion game. We consider both network and general congestion games, and we examine several variants of the problem concerning the structure of the game and its associated cost functions. Many of the problem variants are NP-hard, though we do identify several versions of the games that are solvable in polynomial time. We then investigate existence and the price of anarchy of pure Nash equilibria in k-splittable congestion games with linear costs. A k-splittable congestion game is one in which each player may split its flow on at most k different paths. We identify conditions for the existence of equilibria by providing a series of potential functions. For the price of anarchy, we show an asymptotic lower bound of 2.4 for unweighted k-splittable congestion games and 2.401 for weighted k-splittable congestion games, and an upper bound of 2.618 in both cases. In this thesis we examine four network flow problems arising in the study of transportation, communication, and water networks. The first of these problems is the Integer Equal Flow problem, a network flow variant in which some arcs are restricted to carry equal amounts of flow. Our main contribution is that this problem is not approximable within a factor of 2n(1-epsilon]), for any fixed [epsilon] > 0, where n is the number of nodes in the graph. We extend this result to a number of variants on the size and structure of the arc sets. We next study the Pup Matching problem, a truck routing problem where two commodities ('pups') traversing an arc together in the network incur the arc cost only once. We propose a tighter integer programming formulation for this problem, and we address practical problems that arise with implementing such integer programming solutions. Additionally, we provide approximation and exact algorithms for special cases of the problem where the number of pups is fixed or the total cost in the network is bounded. Our final two problems are on the topic of congestion games, which were introduced in the area of communications networks. by Carol Meyers. Ph.D. 2007-02-20T15:07:21Z 2007-02-20T15:07:21Z 2006 2006 Thesis http://hdl.handle.net/1721.1/35919 76951154 eng 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 164 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Meyers, Carol, Ph. D. Massachusetts Institute of Technology Network flow problems and congestion games : complexity and approximation results |
| title | Network flow problems and congestion games : complexity and approximation results |
| title_full | Network flow problems and congestion games : complexity and approximation results |
| title_fullStr | Network flow problems and congestion games : complexity and approximation results |
| title_full_unstemmed | Network flow problems and congestion games : complexity and approximation results |
| title_short | Network flow problems and congestion games : complexity and approximation results |
| title_sort | network flow problems and congestion games complexity and approximation results |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/35919 |
| work_keys_str_mv | AT meyerscarolphdmassachusettsinstituteoftechnology networkflowproblemsandcongestiongamescomplexityandapproximationresults |