Approximation Algorithms for Combinatorial Optimization Problems with Packing Constraints

点击翻译按钮获取中文摘要

The task of computing an optimal solution to a given (discrete) problem is ubiquitous in computer science and is usually referred to as an combinatorial optimization problem. Many of the naturally arising problems are NP-hard, which makes it unlikely that they admit a polynomial time algorithm solving them to optimality. A natural way to attack NP-hard optimization problems is to develop an approximation algorithm that computes in polynomial time an approximate rather than an optimal solution. The field of approximation algorithms has lead to a plethora of algorithmic techniques. And although this field has already reached a certain level of maturity many interesting and fundamental questions remain open.In particular, there is currently still big gap in understanding how adding even a (seemingly) simple constraint such as a capacity constraint (or, more generally, packing constraints) affects the approximability of the problem. For many fundamental problems (such as facility location or k-median) the basic variant is understood almost completely or at least satisfactorily. Many existing algorithms rely on a close connection to a continuous relaxation of the problem. However, these relaxations often have an unbounded integrality gap under the presence of the above-mentioned constraints and also the gap between the best known approximability and inapproximability bounds are large despite significant efforts by the community.In this project, we will study the approximability of several fundamental optimization problems under the presence of packing constraints. For some of these problems any noteworthy progress would be considered a breakthrough in the community. In other cases, we believe that new results would be a valuable contribution to a more systematic understanding of the presence of such constraints. Our focus lies in investigating the power of recently developed algorithmic tools, for example, rounding (non-standard) extended LP formulations or submodular function optimization, when applied to these problems.In particular, we will study capacitated location problems, capacitated or cardinality-constrained covering problems, network design problems with distance constraints (a special packing constraint). We will also consider soft-constrained variants where violating the constraints is not forbidden but penalized in the objective function.