pith. machine review for the scientific record. sign in

arxiv: 1107.2033 · v1 · submitted 2011-07-11 · 💻 cs.DS

Recognition: unknown

A note on the generalized min-sum set cover problem

Martin Skutella , David P. Williamson
Authors on Pith no claims yet
classification 💻 cs.DS
keywords algorithmproblemapproximationcovergeneralizedmin-sumobtainable
0
0 comments X
read the original 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 $\alpha$-point scheduling to obtain our improvements.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover

    cs.DS 2026-05 unverdicted novelty 6.0

    A 4.509-approximation algorithm for generalized min-sum set cover that improves the prior 4.642 bound via refined LP analysis and new lower-tail bounds on sums of independent Bernoullis.