Technical Report MSC-2016-09

Title: Multiplicative Approximation Algorithms for Generalized Covering and Packing Problems
Authors: Jonathan A. Wagner
Supervisors: Elad Hazan
PDFCurrently accessibly only within the Technion network
Abstract: Approximation of min-max problems is a common task in convex optimization which has many important uses in machine learning and combinatorial optimisation.

Approximations of problems can be divided into two main categories - additive approximations and multiplicative approximations. Additive approximations are usually relevant to general settings, but have runtime that in many cases depends significantly on the magnitude of natural parameters of the problem. Multiplicative approximations on the other hand, are natural for non-negative settings, and unlike the additive case, allow in many cases algorithms that are independent of the magnitude, or width, of the input parameters. This property is also known as width-free running time. Multiplicative approximation can also be useful if the optimum value of the problem is very small. In this case a multiplicative approximation of even 1/2, gives a very small additive approximation which may require much larger running time by additive approximation methods.

Recently, for the case of additive approximation, the use of sampling methods together with low-regret algorithms enabled the development of a general method for approximating an important class of min-max problems. This led to remarkably fast algorithms for several important problems in machine learning. This approach, however, did not address the task of multiplicative approximation.

In this work we present simple schemes based on low regret algorithms that give width-independent multiplicative approximation algorithms for two important classes of non-negative min-max problems - generalized covering and generalized packing. Our main contribution is a novel sampling and speed-up technique that in certain cases can be incorporated into the schemes and lead to very fast algorithms. As an application, we describe the first near-linear time, width-free multiplicative approximation algorithms for Normalized Covering Semi-definite Programming,and for Non-negative Linear Classifier.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2016
To the main CS technical reports page

Computer science department, Technion