Extending the primal-dual 2-approximation algorithm beyond uncrossable set families

• 成果类型: Article; Early Access
• 署名作者: Nutov, Zeev
• 署名单位: Open University Israel
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02240-1
• 发表日期: 2025
• 关键词: APPROXIMATION ALGORITHM

摘要

A set family F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{F}$$\end{document} is uncrossable if A boolean AND B,A boolean OR B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \cap B,A \cup B \in \mathcal{F}$$\end{document} or A\B,B\A is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \setminus B,B \setminus A \in \mathcal{F}$$\end{document} for any A,B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A,B \in \mathcal{F}$$\end{document}. A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993:708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio 2, by a primal-dual algorithm with a reverse delete phase. They asked whether this result extends to a larger class of set families and combinatorial optimization problems. We define a new class of semi-uncrossable set families, when for any A,B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A,B \in \mathcal{F}$$\end{document} we have that A boolean AND B is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \cap B \in \mathcal{F}$$\end{document} and one of A boolean OR B,A\B,B\A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \cup B,A \setminus B ,B \setminus A$$\end{document} is in F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{F}$$\end{document}, or A\B,B\A is an element of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \setminus B,B \setminus A \in \mathcal{F}$$\end{document}. We will show that the Williamson et al. algorithm extends to this new class of families and identify several non-uncrossable algorithmic problems that belong to this class. In particular, we will show that the union of an uncrossable family and a monotone family, or of an uncrossable family that has the disjointness property and a proper family, is a semi-uncrossable family, that in general is not uncrossable. For example, our result implies approximation ratio 2 (improving the previous ratio 4) for the problem of finding a min-cost subgraph H such that H contains a Steiner forest and every connected component of H contains zero or at least k nodes from a given set T of terminals.