A note on the generalized min-sum set cover problem

2011/07/11 by Skutella, Martin, Williamson, David P. · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1107.2033

Abstract

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin. Bansal, Gupta, and Krishnaswamy give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements.

Cited by

• Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error

Related

• Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover
• Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
• A General Framework for Approximating Min Sum Ordering Problems
• On the Approximability of Multistage Min-Sum Set Cover
• An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem