Research Repository

Tight approximation bounds for combinatorial frugal coverage algorithms

Caragiannis, Ioannis and Kaklamanis, Christos and Kyropoulou, Maria (2013) 'Tight approximation bounds for combinatorial frugal coverage algorithms.' Journal of Combinatorial Optimization, 26 (2). pp. 292-309. ISSN 1382-6905

[img]
Preview
PDF
caragian52.pdf - Accepted Version

Download (201kB) | Preview

Abstract

We consider the frugal coverage problem, an interesting variation of set cover defined as follows. Instances of the problem consist of a universe of elements and a collection of sets over these elements; the objective is to compute a subcollection of sets so that the number of elements it covers plus the number of sets not chosen is maximized. The problem was introduced and studied by Huang and Svitkina (Proceedings of the 29th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS), pp. 227–238, 2009) due to its connections to the donation center location problem. We prove that the greedy algorithm has approximation ratio at least 0.782, improving a previous bound of 0.731 in Huang and Svitkina (Proceedings of the 29th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS), pp. 227–238, 2009). We also present a further improvement that is obtained by adding a simple corrective phase at the end of the execution of the greedy algorithm. The approximation ratio achieved in this way is at least 0.806. Finally, we consider a packing based algorithm that uses semi-local optimization, and show that its approximation ratio is not less than 0.872. Our analysis is based on the use of linear programs which capture the behavior of the algorithms in worst-case examples. The obtained bounds are proved to be tight.

Item Type: Article
Uncontrolled Keywords: Frugal coverage; Set cover; Set packing; Approximation algorithms
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 24 Mar 2022 19:10
Last Modified: 24 Mar 2022 19:11
URI: http://repository.essex.ac.uk/id/eprint/32605

Actions (login required)

View Item View Item