{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/224"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/224","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Cost Sharing and Approximation","abstract":"Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems. In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands. We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.","abstract_html":"Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems. In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands. We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.","abstract_has_math":false,"creators":["Martin, Pal"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004-12-13T15:12:33Z","date_published":"2004-12-13T15:12:33Z","updated_at":"2026-11-19T03:14:48Z","subjects":["approximation algorithms","cost sharing","network design","stochastic optimization"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475965"],"render_values":[{"text":"6475965","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/224","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/224","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F224","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Martin, Pal"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2004-12-13T15:12:33Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2004-12-13T15:12:33Z"]},{"key":"dc:date.issued","label":"Date","values":["2004-12-13T15:12:33Z"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["approximation algorithms","cost sharing","network design","stochastic optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475965"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/224"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"d28c69b7-a4fb-4948-9ed1-c2082731302a\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Cost Sharing and Approximation</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2004-12-13T15:12:33Z</PublicationDate> <Authors> <Author> <DisplayName>Martin, Pal</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>approximation algorithms</Keyword> <Keyword>cost sharing</Keyword> <Keyword>network design</Keyword> <Keyword>stochastic optimization</Keyword> <Abstract>Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems. In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands. We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Martin, Pal"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems. In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands. We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["591787 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Cost Sharing and Approximation"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"d28c69b7-a4fb-4948-9ed1-c2082731302a\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Cost Sharing and Approximation</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2004-12-13T15:12:33Z</PublicationDate> <Authors> <Author> <DisplayName>Martin, Pal</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>approximation algorithms</Keyword> <Keyword>cost sharing</Keyword> <Keyword>network design</Keyword> <Keyword>stochastic optimization</Keyword> <Abstract>Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems. In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands. We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Martin, Pal"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Martin, Pal"],"dc:date.accessioned":["2004-12-13T15:12:33Z"],"dc:date.available":["2004-12-13T15:12:33Z"],"dc:date.issued":["2004-12-13T15:12:33Z"],"dc:description.abstract":["Central to this thesis are problems in which a group of users can benefit from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satisfies the needs of a given set of users in a cost-effective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the first part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems. In the second part we proceed in a slightly different direction, applying cost sharing to the design of approximation algorithms. We consider a class of two-stage stochastic problems with recourse. In these problems, we can buy building blocks (edges, facilities, vertices..) in two stages. In the first stage, the elements are relatively inexpensive, but we do not know the requirements of users we will have to serve (we only have a probabilistic forecast of their demands). In the second stage, the actual demands are revealed, and we must buy enough elements (now at a higher price) to satisfy all user demands. We show that whenever the underlying deterministic problem admits a certain type of cost sharing, an extremely simple strategy gives us good approximation guarantees: in the first stage, take several samples from the forecasted distribution, and build a solution that covers all the sampled clients at the low price. When the real users materialize, augment the first stage solution to cover the actual demands. In this way we obtain constant approximation algorithms for stochastic versions of problems like Uncapacitated Facility Location, Steiner tree, Steiner Forest or Vertex Cover."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.extent":["591787 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6475965"],"dc:identifier.uri":["https://hdl.handle.net/1813/224"],"dc:language.iso":["en_US"],"dc:subject":["approximation algorithms","cost sharing","network design","stochastic optimization"],"dc:title":["Cost Sharing and Approximation"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:14:48Z"}