File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Variable-size rectangle covering

TitleVariable-size rectangle covering
Authors
KeywordsBase line
Directional antenna
Polynomial-time algorithms
Running time
Two-dimensional planes
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09), Yellow Mountains, China, 10-12 June 2009. In Lecture Notes in Computer Science, 2009, v. 5573, p. 145-154 How to Cite?
AbstractIn wireless communication networks, optimal use of the directional antenna is very important. The directional antenna coverage (DAC) problem is to cover all clients with the smallest number of directional antennas. In this paper, we consider the variable-size rectangle covering (VSRC) problem, which is a transformation of the DAC problem. There are n points above the base line y=0 of the two-dimensional plane. The target is to cover all these points by minimum number of rectangles, such that the dimension of each rectangle is not fixed but the area is at most 1, and the bottom edge of each rectangle is on the base line y=0. In some applications, the number of rectangles covering any position in the two-dimensional plane is bounded, so we also consider the variation when each position in the plane is covered by no more than two rectangles. We give two polynomial time algorithms for finding the optimal covering. Further, we propose two 2-approximation algorithms that use less running time (O(nlogn) and O(n)). © 2009 Springer Berlin Heidelberg.
DescriptionLNCS v. 5573 is conference proceedings of the 3rd International Conference, COCOA 2009
Persistent Identifierhttp://hdl.handle.net/10722/61165
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-07-13T03:32:19Z-
dc.date.available2010-07-13T03:32:19Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA'09), Yellow Mountains, China, 10-12 June 2009. In Lecture Notes in Computer Science, 2009, v. 5573, p. 145-154en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/61165-
dc.descriptionLNCS v. 5573 is conference proceedings of the 3rd International Conference, COCOA 2009-
dc.description.abstractIn wireless communication networks, optimal use of the directional antenna is very important. The directional antenna coverage (DAC) problem is to cover all clients with the smallest number of directional antennas. In this paper, we consider the variable-size rectangle covering (VSRC) problem, which is a transformation of the DAC problem. There are n points above the base line y=0 of the two-dimensional plane. The target is to cover all these points by minimum number of rectangles, such that the dimension of each rectangle is not fixed but the area is at most 1, and the bottom edge of each rectangle is on the base line y=0. In some applications, the number of rectangles covering any position in the two-dimensional plane is bounded, so we also consider the variation when each position in the plane is covered by no more than two rectangles. We give two polynomial time algorithms for finding the optimal covering. Further, we propose two 2-approximation algorithms that use less running time (O(nlogn) and O(n)). © 2009 Springer Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectBase line-
dc.subjectDirectional antenna-
dc.subjectPolynomial-time algorithms-
dc.subjectRunning time-
dc.subjectTwo-dimensional planes-
dc.titleVariable-size rectangle coveringen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0302-9743&volume=5573&spage=145&epage=154&date=2009&atitle=Variable-size+rectangle+covering-
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-642-02026-1_13en_HK
dc.identifier.scopuseid_2-s2.0-70350640924en_HK
dc.identifier.hkuros162177en_HK
dc.identifier.hkuros166446-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70350640924&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5573en_HK
dc.identifier.spage145en_HK
dc.identifier.epage154en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats