.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithm for Minimum p Union under a Geometric Setting
.png){kind=icon}
PRE
AI
DOI：10.1007/s40305-026-00686-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In a minimum p union problem (MinpU), given a hypergraph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} and an integer p, the goal is to find a set of p hyperedges E 'subset of E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E'\subseteq E$$\end{document} such that the number of vertices covered by E '\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E'$$\end{document} (that is |& xcup;e is an element of E ' e|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\bigcup _{e\in E'}e|$$\end{document}) is minimized. It was known that MinpU is at least as hard as the densest k-subgraph problem. A question is: how about the problem in some geometric settings? In this paper, we consider the unit square MinpU problem (MinpU-US) in which V is a set of points on the plane, and each hyperedge of E consists of a set of points in a unit square, the goal of the MinpU-US problem is to select p squares such that the number of points covered by the union of these p squares is as small as possible. A (11+epsilon,4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\frac{1}{1+\varepsilon },4)$$\end{document}-bicriteria approximation algorithm is presented, that is, the algorithm finds at least p1+epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{p}{1+\varepsilon }$$\end{document} unit squares covering at most 4opt\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4\,opt$$\end{document} points, where opt is the optimal value for the MinpU-US instance (the minimum number of points that can be covered by p unit squares).
Keywords:
Minimum p union
Unit square
Approximation algorithm
Journal
J
IF:
1.1
Papers:
64
Citations:
487