Geometric Optimization Problems with Time-Varying Input

Summary In traditional (combinatorial) optimization problems, first an input instance is specified, and next a solution for this instance is generated and outputted by some computational procedure. In this proposal we deviate from this paradigm by not being interested in finding a single solution; instead, we want to maintain a solution as the input data or parameters of the problem change over time and changing the solution comes at a cost. We will focus on geometric (network) problems. The goal of our research is now to develop algorithms for these problems that maintain a solution to the problem at hand “in a good way.”
Supervisors Mark de Berg (TU/e), Frits Spieksma (TU/e)
PhD Student Arpan Sadhukhan
Location Technische Universiteit Eindhoven (TU/e)