A hybrid algorithm based on a multiple randomized rounding for set multicover problem: Approximation guarantees and experiments

doi:10.1016/j.tcs.2026.115849

A hybrid algorithm based on a multiple randomized rounding for set multicover problem: Approximation guarantees and experiments

2026-03-01

0

PRE

AI

DOI：10.1016/j.tcs.2026.115849

Original

Original request for help

Save

Abstract

En 中文

The paper discusses a subclass of multicovering problems which deals with finding an integer is an element of{0,1}minimizing & sum; such that >=, where is a 0/1matrix of order & times;and is an integer vector. Let & ratio;= min is an element of[] and we assume that the number of ones is bounded by a constant Delta in every row and by 8 in every column. Peleg, Schechtman, and Wool conjectured that unless = , there is no polynomial-time approximation algorithm for the problem with an approximation ratio less than = Delta - + 1. The paper proposes a hybrid algorithm based on multiple randomizedrounding for the problem, which yields an approximation ratio { ( (3+1 ) )} of max 16, 15 1-exp 8 . The algorithm improves over previous results and has no re-728 striction on the parameter 8. Furthermore, experimental results on both synthetic and real-world instances demonstrate that our algorithm consistently outperforms the classical greedy algorithm baselines.

Keywords:

Integer linear program

Hypergraph

Approximation algorithm

Randomized rounding

Set multicover

A hybrid algorithm based on a multiple randomized rounding for set multicover problem: Approximation guarantees and experiments

Abstract

Journal

Organization