Vignettes on robust combinatorial optimization

In this thesis, we design and analyze algorithms for robust combinatorial optimization in various settings. First, we consider the problem of simultaneously maximizing multiple objectives, all monotone submodular, subject to a cardinality constraint. We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose several algorithms (including one with the best achievable asymptotic guarantee for the problem). Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms current practical algorithms in all cases considered. Next, we study the problem of robust maximization of a single monotone submodular function in scenarios where after choosing a feasible set of elements, some elements from the chosen set are adversarially removed. Under some restriction on the number of elements that can be removed, we give the first constant factor approximation algorithms as well as the best possible asymptotic approximation in certain cases. We also give a black box result for the much more general setting of deletion-robust maximization subject to an independence system. Lastly, we consider a robust appointment scheduling problem where the goal is to design simple appointment systems that try to achieve both high server utilization as well as short waiting times, under uncertainty in job processing times. When the order of jobs is fixed and one seeks to find optimal appointment duration for jobs, we give a simple heuristic that achieves the first constant factor (2) approximation. We also give closed form optimal solutions in various special cases that supersede previous work. For the setting where order of jobs is also flexible and under-utilization costs are homogeneous, it was previously shown that an EPTAS exists. We instead focus on simple and practical heuristics, and find a ratio based ordering which is 1.0604 approximate, improving on previous results for similarly practical heuristics.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Udwani, Rajan

Advisor dc:contributor.advisor

• James B. Orlin and Andreas S. Schulz.

• Operations Research Center.

Statement 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/120192

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/120192