Robust and Adaptive Optimization

Optimization is one of the most interesting and well-studied domains in Mathematics and Computer Science. It has attracted the interest of researcher communities from diverse backgrounds for centuries. Some of the optimization problems are harder than others, because of the uncertainties involved in them due to the structure of the problem, or due to the uncertainty in the input data. The uncertainties can be passive or they can be induced actively by an adversary. Many of those problems are NP-Hard. Scheduling problems and spanning tree problems have also attracted the researchers for a long time. In this work, we have developed robust and adaptive algorithms for some problems from the above-mentioned domains. We have provided polynomial-time algorithms for tractable problems. As we investigated many NP-Hard problems, either we have provided polynomial-time algorithms for those problems with special structures, or we have designed approximation algorithms and heuristics for the general problems. We have reported experimental results and the outcomes of comparative studies between different schemes to evaluate those heuristics and approximation algorithms.