An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty
In this paper, we consider the minimum power cover problem with submodular penalty (SPMPC). Given a set <i>U</i> of <i>n</i> users, a set <i>S</i> of <i>m</i> sensors and a penalty function <inline-formula><math xmlns="http://www.w3.org/1...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Computation |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-3197/10/10/189 |
| _version_ | 1797474134524952576 |
|---|---|
| author | Han Dai |
| author_facet | Han Dai |
| author_sort | Han Dai |
| collection | DOAJ |
| description | In this paper, we consider the minimum power cover problem with submodular penalty (SPMPC). Given a set <i>U</i> of <i>n</i> users, a set <i>S</i> of <i>m</i> sensors and a penalty function <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>π</mi><mo>:</mo><msup><mn>2</mn><mi>U</mi></msup><mo>→</mo><msub><mi mathvariant="double-struck">R</mi><mo>+</mo></msub></mrow></semantics></math></inline-formula> on the plane, the relationship that adjusts the power <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow></semantics></math></inline-formula> of each sensor <i>s</i> and its corresponding radius <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow></semantics></math></inline-formula> is: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo><mi>c</mi><mo>·</mo><mi>r</mi><msup><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mi>α</mi></msup></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>. The SPMPC problem is to determine the power assignment on each sensor such that each user <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>∈</mo><mi>U</mi></mrow></semantics></math></inline-formula> is either covered by the sensor or penalized and the sum of the total power consumed by sensors in <i>S</i> plus the penalty of all uncovered users is minimized, the penalty here is determined by the submodular function. Based on the primal dual technique, we design an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>α</mi><mo>)</mo></mrow></semantics></math></inline-formula>-approximation algorithm. |
| first_indexed | 2024-03-09T20:26:47Z |
| format | Article |
| id | doaj.art-ff6bc013e11f43648a67617a5337ddb5 |
| institution | Directory Open Access Journal |
| issn | 2079-3197 |
| language | English |
| last_indexed | 2024-03-09T20:26:47Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Computation |
| spelling | doaj.art-ff6bc013e11f43648a67617a5337ddb52023-11-23T23:35:54ZengMDPI AGComputation2079-31972022-10-01101018910.3390/computation10100189An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular PenaltyHan Dai0School of Mathematics and Statistics, Yunnan University, Kunming 650504, ChinaIn this paper, we consider the minimum power cover problem with submodular penalty (SPMPC). Given a set <i>U</i> of <i>n</i> users, a set <i>S</i> of <i>m</i> sensors and a penalty function <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>π</mi><mo>:</mo><msup><mn>2</mn><mi>U</mi></msup><mo>→</mo><msub><mi mathvariant="double-struck">R</mi><mo>+</mo></msub></mrow></semantics></math></inline-formula> on the plane, the relationship that adjusts the power <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow></semantics></math></inline-formula> of each sensor <i>s</i> and its corresponding radius <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow></semantics></math></inline-formula> is: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo><mi>c</mi><mo>·</mo><mi>r</mi><msup><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mi>α</mi></msup></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>. The SPMPC problem is to determine the power assignment on each sensor such that each user <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>∈</mo><mi>U</mi></mrow></semantics></math></inline-formula> is either covered by the sensor or penalized and the sum of the total power consumed by sensors in <i>S</i> plus the penalty of all uncovered users is minimized, the penalty here is determined by the submodular function. Based on the primal dual technique, we design an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>α</mi><mo>)</mo></mrow></semantics></math></inline-formula>-approximation algorithm.https://www.mdpi.com/2079-3197/10/10/189power coversubmodular functionprimal dualapproximation algorithm |
| spellingShingle | Han Dai An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty Computation power cover submodular function primal dual approximation algorithm |
| title | An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty |
| title_full | An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty |
| title_fullStr | An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty |
| title_full_unstemmed | An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty |
| title_short | An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty |
| title_sort | improved approximation algorithm for the minimum power cover problem with submodular penalty |
| topic | power cover submodular function primal dual approximation algorithm |
| url | https://www.mdpi.com/2079-3197/10/10/189 |
| work_keys_str_mv | AT handai animprovedapproximationalgorithmfortheminimumpowercoverproblemwithsubmodularpenalty AT handai improvedapproximationalgorithmfortheminimumpowercoverproblemwithsubmodularpenalty |