arXiv Open Access 2022

Constant approximation for fault-tolerant median problems via iterative rounding

Shichuan Deng

Lihat Sumber

Abstrak

In this paper, we study the fault-tolerant matroid median and fault-tolerant knapsack median problems. These two problems generalize many fundamental clustering and facility location problems, such as uniform fault-tolerant $k$-median, uniform fault-tolerant facility location, matroid median, knapsack median, etc. We present a versatile iterative rounding framework and obtain a unifying constant-factor approximation algorithm.

Topik & Kata Kunci

cs.DS

Penulis (1)

Shichuan Deng

Format Sitasi

APA MLA BibTeX

Deng, S. (2022). Constant approximation for fault-tolerant median problems via iterative rounding. https://arxiv.org/abs/2205.04744

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2022
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓