{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/35919"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/35919","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Network flow problems and congestion games : complexity and approximation results","abstract":"(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.","abstract_html":"(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.","abstract_has_math":false,"creators":["Meyers, Carol, Ph. D. Massachusetts Institute of Technology"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Operations Research Center.","school":null,"contributors":[],"advisors":["Andreas S. Schulz."],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006","date_published":"2006","updated_at":"2026-07-22T22:20:53Z","subjects":["Operations Research Center."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/35919","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Andreas S. Schulz."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Operations Research Center."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Operations Research Center."]},{"key":"dc:creator","label":"Author","values":["Meyers, Carol, Ph. D. Massachusetts Institute of Technology"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2007-02-20T15:07:21Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2007-02-20T15:07:21Z"]},{"key":"dc:date.issued","label":"Date","values":["2006"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Operations Research Center."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/35919"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)."]},{"key":"dc:description.abstract","label":"Abstract","values":["(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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Network flow problems and congestion games : complexity and approximation results"]}]}],"canonical_facts":{"dc:contributor.advisor":["Andreas S. Schulz."],"dc:contributor.department":["Massachusetts Institute of Technology. Operations Research Center."],"dc:contributor.other":["Massachusetts Institute of Technology. Operations Research Center."],"dc:creator":["Meyers, Carol, Ph. D. Massachusetts Institute of Technology"],"dc:date.accessioned":["2007-02-20T15:07:21Z"],"dc:date.available":["2007-02-20T15:07:21Z"],"dc:date.issued":["2006"],"dc:description":["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)."],"dc:description.abstract":["(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."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/35919"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc: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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Operations Research Center."],"dc:title":["Network flow problems and congestion games : complexity and approximation results"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:53Z"}