# 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.