Minimizing the Maximum Moving Cost of Interval Coverage

被引：5

作者：

Wang, Haitao ^{[1
]}

Zhang, Xiao ^{[2
]}

机构：

[1] Utah State Univ, Dept Comp Sci, Logan, UT 84322 USA

[2] City Univ Hong Kong, Dept Comp Sci, Kowloon Tong, Hong Kong, Peoples R China

来源：

ALGORITHMS AND COMPUTATION, ISAAC 2015 | 2015年 / 9472卷

基金：

美国国家科学基金会;

关键词：

D O I：

10.1007/978-3-662-48971-0_17

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we study an interval coverage problem. We are given n intervals of the same length on a line L and a line segment B on L. Each interval has a nonnegative weight. The goal is to move the intervals along L such that every point of B is covered by at least one interval and the maximum moving cost of all intervals is minimized, where the moving cost of each interval is its moving distance times its weight. Algorithms for the "unweighted" version of this problem have been given before. In this paper, we present a first-known algorithm for this weighted version and our algorithm runs in O(n(2) log n log log n) time. The problem has applications in mobile sensor barrier coverage.

引用

页码：188 / 198

页数：11

共 50 条

[31] On the Range Assignment in Wireless Sensor Networks for Minimizing the Coverage-Connectivity Cost
Das, Sajal K.
Kapelko, Rafal
ACM TRANSACTIONS ON SENSOR NETWORKS, 2021, 17 (04)
[32] Minimizing the cost of availability of coverage from a constellation of satellites: Evaluation of optimization methods
Kelley, Clifford
Dessouky, Maged
Systems Engineering, 2004, 7 (02) : 113 - 122
[33] Pareto Minimizing Total Completion Time and Maximum Cost with Positional Due Indices
Gao Y.
Yuan J.-J.
Journal of the Operations Research Society of China, 2015, 3 (3) : 381 - 387
[34] Minimizing maximum cost on a single machine with two competing agents and job rejection
Mor, Baruch
Mosheiov, Gur
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2016, 67 (12) : 1524 - 1531
[35] Minimizing maximum indegree
Venkateswaran, V
DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) : 374 - 378
[36] ON MINIMIZING MAXIMUM ERRORS
PEARSON, JB
BAMIEH, B
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1990, 35 (05) : 598 - 601
[37] A Method for Maximum Coverage of the Territory by Sensors with Minimization of Cost and Assessment of Survivability
Petrivskyi, Volodymyr
Bychkov, Oleksii
Shevchenko, Viktor
Martsenyuk, Vasyl
Bernas, Marcin
APPLIED SCIENCES-BASEL, 2022, 12 (06):
[38] Sustainable Lighting Layout in Urban Areas: Maximizing Implicit Coverage and Minimizing Installation Cost
Hammad, Ahmed W. A.
Akbarnezhad, Ali
FRONTIERS IN BUILT ENVIRONMENT, 2018, 4
[39] TWO-AGENT SCHEDULING OF MINIMIZING TOTAL WEIGHTED LATE WORK AND MAXIMUM COST
Geng, Zhichao
Lu, Lingfa
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2025, : 3648 - 3667
[40] Bicriteria scheduling on an unbounded parallel-batch machine for minimizing makespan and maximum cost
Li, Shuguang
Geng, Zhichao
INFORMATION PROCESSING LETTERS, 2023, 180

← 1 2 3 4 5 →