Approximating Packing Problems
Faculty of Informatics - Academic Studies Administration
Date: 22 October 2025 / 10:00 - 13:00
USI East Campus, Room D2.19
You are cordially invited to attend the PhD Dissertation Defence of Antoine Tinguely on Wednesday 22 October 2025 at 10:00 in room D2.19.
Abstract:
Many optimization problems are NP-hard, meaning that there are most likely no fast (i.e., polynomial-time) algorithms to solve them. An alternative are approximation algorithms, which, in polynomial time, do not compute an exact solution but a solution that is guaranteed to lie within a fixed factor of the optimum. This proposal addresses packing problems, i.e., problems where the goal is to select some items such that they satisfy some packing constraints while maximizing the profit of the selected items. Notable examples are Knapsack, Maximum Independent Set and Maximum Throughput scheduling problems. We present a general framework that can be applied on a family of dynamic programs for packing problems to add further constraints on the problem efficiently. We also present an algorithm to approximate a geometric independent set problem as well as an approximation algorithm for scheduling job under varying capacity constraints.
Dissertation Committee:
- Prof. Fabrizio Grandoni, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Andrea Emilio Rizzoli, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Tobias Moemke, University of Augsburg, Germany (External Member)
- Prof. Andreas Wiese, TU Munich, Germany (External Member)