Efficiency of Simple Algorithms

 

Simple Approximation Algorithms for Covering and Packing Integer Programs — The Greedy Algorithm and Beyond

Primal-dual methods have a longstanding history as a tool which proves approximation guarantees for solutions to combinatorial optimization problems. These methods also play a central role in this project.

There is a simple algorithm which can be applied to many combinatorial optimization problems in order to obtain feasible solutions: the primal-dual greedy algorithm [1]. The algorithm uses a primal-dual problem formulation of a combinatorial optimization problem in order to simultaneously find a pair of primal and dual feasible solutions. Information from the dual solution is used in order to guide the algorithm towards a good primal solution which is computed in a greedy fashion. For many problems, variants of this technique can be used in order to obtain optimum solutions - for example polymatroids - or solutions with bounded approximation guarantee - for example knapsack cover, vertex cover, and various network design problems.

In this research project, we are interested in characterizations of problem formulations which ensure that simple algorithms obtain feasible solutions with a good approximation guarantee. In a preliminary work, for the well-known primal-dual greedy algorithm, we were able to provide a precise characterization of covering integer programs with corresponding matching lower and upper bounds on the approximation guarantee achieved by the greedy algorithm [2]. In the future, we are interested in generalizations of these results towards more general algorithms which are no longer restricted to greedy decisions in the primal space.

  • [1] J. Edmonds. Submodular Functions, Matroids, and Certain Polyhedra. 1970
  • [2] B. Peis, J. Verschae, A. Wierz. The Primal-Dual Greedy Algorithm for Weighted Covering Problems. 2017

This project is contributed by Britta Peis, José Verschae, and Andreas Wierz.