Semi online problems

RWTH Publications (RWTH Aachen)

Abstract

Assume you have an arbitrary problem. Likely, you will then try to find a good solution for it. If you are fully aware of the situation, the future, and your options with their consequences, making a good decision is usually possible. However, often you do not have all the necessary information but need to decide anyway. Luckily, this does not imply you need to decide completely in the dark. You also do not have to stick to the decisions made if new information appears. In this thesis, we will discuss two approaches that help to deal with those problems, as they are modeled best between classical offline and online problems: Often, a decision maker is allowed to delay some decisions. In real life, often such options exist, even though it may not for free: If you are considering whether to book something, purchasing some insurance that allows for cancellation might be possible. In finance, buying options allows you to decide at a later point, but again, this does not come for free. In this thesis, various problems are studied within this Reservation Setting: For two variants of the Secretary Problem, the Simple Knapsack with Removability, and the Vertex Cover, we provide matching upper and lower bounds for the whole range of potential reservation costs from zero to expensive. For the General Knapsack and general vertex deletion problems, such as Feedback Vertex Set, we provide asymptotically tight bounds. Assuming that a setting is either in the complete darkness of an online or with full knowledge of an offline problem is probably even more unrealistic: Usually, you might not have all the information available when deciding, but perhaps a rough overview based on experience or machine learning. Even if the necessary data is available, often it is not exact due to e.g., rounding. In those cases, you will likely have this rough overview of the information available from the beginning. More details will likely be available when decisions need to be made, as is known from online problems. Also in this setting, various problems are studied and called a problem with Estimates: For the Simple Knapsack and Simple Knapsack with Removability, as well as for a restricted version of Bin Packing and Graph Exploration, we provide tight bounds for all accuracy factors, and present bounds for Bin Packing and Graph Exploration. Additionally, we present bounds and an algorithm for the Online Feedback Vertex Set. As it is a natural online problem with non-trivial structure, it is surprising that its study is just initiated within this thesis.

Authors 1

1. Matthias Gehnen corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen