- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Restricted Strip Covering and the Sensor Cover Problem
Restricted Strip Covering and the Sensor Cover Problem
Adam L. Buchsbaum
?
Alon Efrat
?
Shaili Jain
?
Suresh Venkatasubramanian
§
Ke Yi
?
Abstract
Suppose we are given a set of objects that cover a region and a
duration associated with each object. Viewing the objects as jobs,
can we schedule their beginning times to maximize the length of
time that the original region remains covered? We call this problem
the SENSOR COVER PROBLEM. It arises in the context of covering
a region with sensors. For example, suppose you wish to monitor
activity along a fence (interval) by sensors placed at various fixed
locations. Each sensor has a range (also an interval) and limited
battery life. The problem is then to schedule when to turn on the
sensors so that the fence is fully monitored for as long as possible.
This one-dimensional problem involves intervals on the real
line. Associating a duration to each yields a set of rectangles
in space and time, each specified by a pair of fixed horizontal
endpoints and a height. The objective is to assign a bottom
position to each rectangle (by moving them up or down) so as
to maximize the height at which the spanning interval is fully
covered. We call this one-dimensional problem RESTRICTED
STRIP COVERING. If we replace the covering constraint by a
packing constraint (rectangles may not overlap, and the goal is to
minimize the highest point covered), then the problem becomes
identical to DYNAMIC STORAGE ALLOCATION, a well-studied
scheduling problem, which is in turn a restricted case of the well
known problem STRIP PACKING.
We present a collection of algorithms for RESTRICTED STRIP
COVERING. We show that the problem is NP-hard and present an
O(log log log n)-approximation algorithm. We also present better
approximation or exact algorithms for some special cases, includ-
ing when all intervals have equal width. For the general SEN-
SOR COVER PROBLEM, we distinguish between cases in which
elements have uniform or variable durations. The resu
您可能关注的文档
- Ordering dynamics with two non-excluding options Bilingualism in language competition.pdf
- Organic resource management in banana-based cropping systems of the Lake Victoria Basin, Uganda.pdf
- Orientation Competition in Cortical Filters - An Application to Face Recognition.pdf
- Organotrifluoroborate salts.pdf
- Orkot轴承国外业绩表.pdf
- Origin of the viewing-angle dependence of the optical continuum emission in quasars.pdf
- Oscillation of Tc depending on the number of CuO2 planes in the cuprates.pdf
- Orthologs of t he Class A4 Heat Shock Transcription Factor HsfA4a Confer Cadmium T olerance in Wheat.pdf
- Ostara-WASSTRIP-Brochure-FINAL-Web.pdf
- ourdearamy-100424101830-phpapp02.pptx
文档评论(0)