Back
2025INF016.pdf
Doctoral thesis

Approximating packing problems

  • 2025

PhD: Università della Svizzera italiana

Approximation algorithm
Packing
Scheduling
Randomized algorithms
Computational geometry
English 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, compute a solution that is not necessarily exact but that is guaranteed to lie within a fixed factor of the optimum. This thesis 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. We design approximation algorithms for some NP-hard packing problems. More specifically , we obtain the three following results. To model restrictions like resource limitations, fairness constraints or quotas, it is desirable to add one or more budget constraints to a packing problem. Many packing problems can be solved or approximated by dynamic programming. We present a randomized meta-algorithm that can be applied on a family of dynamic programs for packing problems to incorporate budget constraints on the problems efficiently. A polygon is d-oriented if it is convex and its facets are parallel to d given orientations. In the Maximum Independent Set of Polygons, we are given some polygons placed on the plane, and the goal is to find a maximum-cardinality subset of those polygons that do not intersect. We present an O(d)-approximation algorithm for the Maximum Independent Set of d-oriented Polygons, based on dynamic programming. In the Unsplittable Flow on a Path problem with Time Windows, the goal is to schedule some jobs within their respective time windows on a time axis with varying capacity. We present a (2+ε)-approximation algorithm for this problem based on a divide-and-conquer scheme.
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1333906
Statistics
Document views: 0 File downloads:
  • 2025INF016.pdf: 0