{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/122890"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/122890","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Combinatorial incremental problems","abstract":"We study the class of Incremental Combinatorial optimization problems, where solutions are evaluated as they are built, as opposed to only measuring the performance of the final solution. Even though many of these problems have been studied, it has' usually been in isolation, so the first objective of this document is to present them under the same framework. We present the incremental analog of several classic combinatorial problems, and present efficient algorithms to find approximate solutions to some of these problems, either improving, or giving the first known approximation guarantees. We present unifying techniques that work for general classes of incremental optimization problems, using fundamental properties of the underlying problem, such as monotonicity or convexity, and relying on algorithms for the non-incremental version of the problem as subroutines. In Chapter 2 we give an e-approximation algorithm for general incremental minimization problems, improving the best approximation guarantee for the incremental version of the shortest path problem. In Chapter 3 we show constant approximation algorithms for several subclasses of incremental maximization problems, including e/2e-1approximation for the maximum weight matching problem, and a e/e+1 approximation for submodular valuations. In Chapter 4 we introduce a discrete-concavity property that allows us to give constant approximation guarantees to several problems, including an asymptotic 0.85-approximation for the incremental maximum flow with unit capacities, and a 0.9-approximation for incremental maximum cardinality matching, incremental maximum stable set in claw free graphs and incremental maximum size common independent set of two matroids.","abstract_html":"We study the class of Incremental Combinatorial optimization problems, where solutions are evaluated as they are built, as opposed to only measuring the performance of the final solution. Even though many of these problems have been studied, it has' usually been in isolation, so the first objective of this document is to present them under the same framework. We present the incremental analog of several classic combinatorial problems, and present efficient algorithms to find approximate solutions to some of these problems, either improving, or giving the first known approximation guarantees. We present unifying techniques that work for general classes of incremental optimization problems, using fundamental properties of the underlying problem, such as monotonicity or convexity, and relying on algorithms for the non-incremental version of the problem as subroutines. In Chapter 2 we give an e-approximation algorithm for general incremental minimization problems, improving the best approximation guarantee for the incremental version of the shortest path problem. In Chapter 3 we show constant approximation algorithms for several subclasses of incremental maximization problems, including e/2e-1approximation for the maximum weight matching problem, and a e/e+1 approximation for submodular valuations. In Chapter 4 we introduce a discrete-concavity property that allows us to give constant approximation guarantees to several problems, including an asymptotic 0.85-approximation for the incremental maximum flow with unit capacities, and a 0.9-approximation for incremental maximum cardinality matching, incremental maximum stable set in claw free graphs and incremental maximum size common independent set of two matroids.","abstract_has_math":false,"creators":["Unda Surawski, Francisco T."],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Mathematics","school":null,"contributors":[],"advisors":["Michel X. Goemans."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-07-22T22:21:23Z","subjects":["Mathematics."],"languages":["eng"],"rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/122890","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Michel X. Goemans."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Mathematics","Math"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Mathematics."]},{"key":"dc:creator","label":"Author","values":["Unda Surawski, Francisco T."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-11-12T17:42:00Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-11-12T17:42:00Z"]},{"key":"dc:date.issued","label":"Date","values":["2018"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written 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":["https://hdl.handle.net/1721.1/122890"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 95-98)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We study the class of Incremental Combinatorial optimization problems, where solutions are evaluated as they are built, as opposed to only measuring the performance of the final solution. Even though many of these problems have been studied, it has' usually been in isolation, so the first objective of this document is to present them under the same framework. We present the incremental analog of several classic combinatorial problems, and present efficient algorithms to find approximate solutions to some of these problems, either improving, or giving the first known approximation guarantees. We present unifying techniques that work for general classes of incremental optimization problems, using fundamental properties of the underlying problem, such as monotonicity or convexity, and relying on algorithms for the non-incremental version of the problem as subroutines. In Chapter 2 we give an e-approximation algorithm for general incremental minimization problems, improving the best approximation guarantee for the incremental version of the shortest path problem. In Chapter 3 we show constant approximation algorithms for several subclasses of incremental maximization problems, including e/2e-1approximation for the maximum weight matching problem, and a e/e+1 approximation for submodular valuations. In Chapter 4 we introduce a discrete-concavity property that allows us to give constant approximation guarantees to several problems, including an asymptotic 0.85-approximation for the incremental maximum flow with unit capacities, and a 0.9-approximation for incremental maximum cardinality matching, incremental maximum stable set in claw free graphs and incremental maximum size common independent set of two matroids."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Combinatorial incremental problems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Michel X. Goemans."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Mathematics","Math"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Mathematics."],"dc:creator":["Unda Surawski, Francisco T."],"dc:date.accessioned":["2019-11-12T17:42:00Z"],"dc:date.available":["2019-11-12T17:42:00Z"],"dc:date.issued":["2018"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 95-98)."],"dc:description.abstract":["We study the class of Incremental Combinatorial optimization problems, where solutions are evaluated as they are built, as opposed to only measuring the performance of the final solution. Even though many of these problems have been studied, it has' usually been in isolation, so the first objective of this document is to present them under the same framework. We present the incremental analog of several classic combinatorial problems, and present efficient algorithms to find approximate solutions to some of these problems, either improving, or giving the first known approximation guarantees. We present unifying techniques that work for general classes of incremental optimization problems, using fundamental properties of the underlying problem, such as monotonicity or convexity, and relying on algorithms for the non-incremental version of the problem as subroutines. In Chapter 2 we give an e-approximation algorithm for general incremental minimization problems, improving the best approximation guarantee for the incremental version of the shortest path problem. In Chapter 3 we show constant approximation algorithms for several subclasses of incremental maximization problems, including e/2e-1approximation for the maximum weight matching problem, and a e/e+1 approximation for submodular valuations. In Chapter 4 we introduce a discrete-concavity property that allows us to give constant approximation guarantees to several problems, including an asymptotic 0.85-approximation for the incremental maximum flow with unit capacities, and a 0.9-approximation for incremental maximum cardinality matching, incremental maximum stable set in claw free graphs and incremental maximum size common independent set of two matroids."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/122890"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Mathematics."],"dc:title":["Combinatorial incremental problems"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral"]},"updated_at":"2026-07-22T22:21:23Z"}