2026-09-19T17:57:33.585832200Zhttps://opus.uleth.ca/server/oai/request
oai:opus.uleth.ca:10133/47742017-02-06T15:24:27Zcom_10133_3346com_10133_1com_10133_296col_10133_3347col_10133_298
ULethbridge OPUS Repository supervisor Benkoczi, Robert author Thom, Mark author University of Lethbridge. Faculty of Arts and Science 2017-02-03T16:21:54Z 2017-02-03T16:21:54Z 2017 https://hdl.handle.net/10133/4774 Covering problems fall within the broader category of facility location, a branch of combinatorial optimization concerned with the optimal placement of service facilities in some geometric space. This thesis considers two classes of covering problems. The first, Covering with Variable Capacities (CVC), was introduced in [1] and adds a notion of capacity to the classical Uncapacitated Facility Location problem. That is, each facility has a fixed maximum quantity of clients it can serve. The objective of each variant of CVC is either to serve all clients, the greatest number of clients possible, or all clients using the least number of facilities possible. We provide approximation algorithms, and in a few select cases, optimal algorithms, for all three variants of CVC. The second class of covering problems is barrier coverage. When the purpose of coverage is surveillance rather than service, a cost effective approach to the problem of intruder detection is to place sensors along the boundary, or barrier, of the surveilled region. A barrier coverage is complete when any intrusion is sure to be detected by some sensor. We limit our consideration of barrier coverage to the one-dimensional case, where the region is a line segment. Sensors are themselves line segments, whose span forms a detection range. The objective of barrier coverage as considered here is to form a complete barrier coverage while minimizing the total movement cost, the sum of the weighted distances moved by each sensor in the solution. We show that, by assuming the sensors lie in initial positions where their detection ranges are disjoint from the barrier, one-dimensional barrier coverage can be solved with an FPTAS. Along the way to developing the FPTAS, we give a fast, simple 2-approximation algorithm for weighted disjoint barrier coverage. en_US approximation algorithms covering problems facility location Investigations on two classes of covering problems Thesis PGI+VW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdlIHwgTm9uLUV4Y2x1c2l2ZSBUaGVzaXMgTGljZW5zZSBBZ3JlZW1lbnQ8L2I+DQo8cD5JbiBjb25zaWRlcmF0aW9uIG9mIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgYWdyZWVpbmcgdG8gbWFrZSB5b3VyIHRoZXNpcy9kaXNzZXJ0YXRpb24gKHRoZSAiVGhlc2lzIikgYXZhaWxhYmxlIHRvIGludGVyZXN0ZWQgcGVyc29ucywgeW91IGFncmVlIGFzIGZvbGxvd3M6IDwvcD4NCjxvbD4NCjxsaT5Zb3UgaGVyZWJ5IGdyYW50IHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgYSBub24tZXhjbHVzaXZlLCB3b3JsZHdpZGUsIGlycmV2b2NhYmxlLCByb3lhbHR5LWZyZWUgbGljZW5zZSB0byBhcmNoaXZlLCBwcmVzZXJ2ZSwgcHJvZHVjZSwgcmVwcm9kdWNlLCBwdWJsaXNoLCBjb21tdW5pY2F0ZSwgY29udmVydCBpbnRvIGFueSBmb3JtYXQsIGNvbW11bmljYXRlIGFuZCBkaXN0cmlidXRlIHRoZSBUaGVzaXMsIGluY2x1ZGluZyB0aGUgVGhlc2lzIGFic3RyYWN0LCBpbiBhbnkgZm9ybWF0IGFuZCBpbiBhbnkgbWVkaXVtIGZvciBub24tY29tbWVyY2lhbCBwdXJwb3NlcyBmb3IgdGhlIGZ1bGwgdGVybSBvZiB0aGUgY29weXJpZ2h0LCBpbmNsdWRpbmcgYnV0IG5vdCBsaW1pdGVkIHRvIHRoZSByaWdodCB0bzoNCjxvbCB0eXBlPSJhIj48bGk+bWFrZSB0aGUgVGhlc2lzIGF2YWlsYWJsZSBpbiBwcmludCBvciBvbmxpbmUgYnkgdGVsZWNvbW11bmljYXRpb24gdG8gdGhlIHB1YmxpYywgaW5jbHVkaW5nIHZpYSB0aGUgaW50ZXJuZXQgYW5kIGZhY3NpbWlsZSB0cmFuc21pc3Npb24sIGZvciBub24tY29tbWVyY2lhbCBwdXJwb3Nlczs8L2xpPg0KPGxpPmRpc3RyaWJ1dGUgdGhlIFRoZXNpcyB0aHJvdWdoIHRoZSBsaWJyYXJ5LCBpbnRlcmxpYnJhcnkgYW5kIHB1YmxpYyBsb2FuOzwvbGk+DQo8bGk+ZGlnaXRpemUsIHBob3RvY29weSBhbmQgbWljcm9maWNoZSB0aGUgVGhlc2lzOyBhbmQgPC9saT4NCjxsaT5zdWItbGljZW5jZSB0byBMaWJyYXJ5IGFuZCBBcmNoaXZlcyBDYW5hZGEgYW55IG9mIHRoZSBhY3Rpb25zIG1lbnRpb25lZCBhYm92ZS4gPC9saT48L29sPjwvbGk+DQo8bGk+WW91IGNvbmZpcm0gdGhlIGZvbGxvd2luZyBzdGF0ZW1lbnRzIHRvIGJlIHRydWUgYW5kIGFjY3VyYXRlOg0KPG9sIHR5cGU9ImEiPjxsaT55b3UgaGF2ZSB0aGUgcmlnaHQgYW5kIGF1dGhvcml0eSB0byBncmFudCB0aGUgcmlnaHRzIHNldCBvdXQgaW4gdGhpcyBsaWNlbnNlOyA8L2xpPg0KPGxpPnRoZSBUaGVzaXMgaXMgeW91ciBvcmlnaW5hbCB3b3JrIGFuZCBpcyBhbiB1bi1hbWVuZGVkIGNvcHkgb2YgdGhlIGZpbmFsIHZlcnNpb24gYXBwcm92ZWQgYnkgdGhlIERlYW4gb2YgdGhlIFNjaG9vbCBvZiBHcmFkdWF0ZSBTdHVkaWVzOyA8L2xpPg0KPGxpPnRoZSBUaGVzaXMgZG9lcyBub3QgaW5mcmluZ2UgdGhlIGNvcHlyaWdodCBvciBpbnRlbGxlY3R1YWwgcHJvcGVydHkgcmlnaHRzIG9mIGFueSBvdGhlciBwZXJzb247IDwvbGk+DQo8bGk+aWYgdGhlIFRoZXNpcyBjb250YWlucyBtYXRlcmlhbCBmb3Igd2hpY2gsIHVuZGVyIHRoZSB0ZXJtcyBvZiB0aGUgQ29weXJpZ2h0IEFjdCwgd3JpdHRlbiBwZXJtaXNzaW9uIG9mIHRoZSBjb3B5cmlnaHQgb3duZXIocykgaXMgcmVxdWlyZWQgdG8gaW5jbHVkZSB0aGUgd29yayAob3IgcGFydCB0aGVyZW9mLCBhcyB0aGUgY2FzZSBtYXkgYmUpIGluIHRoZSBUaGVzaXMsIHRoZW4gYm90aCBvZiB0aGUgZm9sbG93aW5nIGFwcGx5Og0KPG9sIHR5cGU9ImkiPjxsaT50aGUgbWF0ZXJpYWwgaGFzIGJlZW4gY2xlYXJseSBhbmQgYXBwcm9wcmlhdGVseSBpZGVudGlmaWVkIGFuZCBhY2tub3dsZWRnZWQ7IGFuZCA8L2xpPg0KPGxpPnlvdSBoYXZlIG9idGFpbmVkIHdyaXR0ZW4gcGVybWlzc2lvbiBvZiB0aGUgY29weXJpZ2h0IG93bmVyKHMpLCBmb3IgdGhlIGZ1bGwgdGVybSBvZiBjb3B5cmlnaHQgcHJvdGVjdGlvbiwgdG8gaW5jbHVkZSB0aGUgd29yayAob3IgcGFydCB0aGVyZW9mLCBhcyB0aGUgY2FzZSBtYXkgYmUpIGluIHRoZSBUaGVzaXMgYW5kIHRvIGdyYW50IHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgdGhlIHJpZ2h0cyBzZXQgb3V0IGluIHRoaXMgbGljZW5zZTsgPC9saT48L29sPiA8L2xpPg0KPGxpPiB0aGUgVGhlc2lzIGRvZXMgbm90IGNvbnRhaW4gYW55IGNvbmZpZGVudGlhbCBvciBwcm9wcmlldGFyeSBpbmZvcm1hdGlvbiBiZWxvbmdpbmcgdG8gb3RoZXJzLCBvdGhlciB0aGFuIGluZm9ybWF0aW9uIGluY2x1ZGVkIHVuZGVyIFNlY3Rpb24gMiBkKSBhYm92ZTsgPC9saT4NCjxsaT50aGUgVGhlc2lzIGRvZXMgbm90IGNvbnRhaW4gYW55IGxpYmVsb3VzIG9yIG90aGVyIHVubGF3ZnVsIG1hdHRlciBhbmQgZG9lcyBub3QgaW52YWRlIHRoZSBwcml2YWN5IG9mIGFueSBwZXJzb25zOyBhbmQgPC9saT4NCjxsaT50aGVyZSBhcmUgbm8gdW5leHBpcmVkIHB1YmxpY2F0aW9uIGRlbGF5cyBvbiB0aGUgZGlzdHJpYnV0aW9uIG9mIHRoZSBUaGVzaXMuIDwvbGk+PC9vbD4gPC9saT4NCjxsaT5Zb3UgYXJlIGF3YXJlIHRoYXQgeW91IHJldGFpbiB5b3VyIGNvcHlyaWdodCBvd25lcnNoaXAgYW5kIG1vcmFsIHJpZ2h0cyBpbiB0aGUgVGhlc2lzIGFuZCBtYXkgZGVhbCB3aXRoIHRoZSBUaGVzaXMgaW4gYW55IHdheSBjb25zaXN0ZW50IHdpdGggdGhlIHJpZ2h0cyBncmFudGVkIHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgaW4gdGhpcyBsaWNlbnNlLiBZb3UgdW5kZXJ0YWtlIHRvIHN1Ym1pdCB5b3VyIFRoZXNpcywgaW5jbHVkaW5nIHRoZSBUaGVzaXMgYWJzdHJhY3QsIHRocm91Z2ggdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZSB0byBMaWJyYXJ5IGFuZCBBcmNoaXZlcyBDYW5hZGEuIFlvdSBwcm9taXNlIHRvIGluZm9ybSBhbnkgcGVyc29uIHRvIHdob20geW91IG1heSBoZXJlYWZ0ZXIgYXNzaWduIG9yIGxpY2Vuc2UgeW91ciBjb3B5cmlnaHQgaW4geW91ciBUaGVzaXMgb2YgdGhlIHJpZ2h0cyBncmFudGVkIHRvIHRoZSBVbml2ZXJzaXR5IG9mIExldGhicmlkZ2UgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWdyZWUgdGhhdCB0aGUgVW5pdmVyc2l0eSBvZiBMZXRoYnJpZGdlIGlzIG5vdCByZXNwb25zaWJsZSBmb3IgYW55IG1pc3VzZSBvZiB0aGUgVGhlc2lzIGJ5IHRoaXJkIHBhcnRpZXMgd2hvIGFjY2VzcyB0aGUgVGhlc2lzIHRocm91Z2ggdGhlIFVuaXZlcnNpdHkgb2YgTGV0aGJyaWRnZeKAmXMgZmFjaWxpdGllcy48L2xpPjwvb2w+ URL http://localhost:4000/bitstreams/ee977e70-3074-4996-82f7-6119f19d8cb2/download File MD5 9bb418c2973a0d7621beef34ff50a9c6 886973 application/pdf THOM_MARK_PHD_2017.pdf URL http://localhost:4000/bitstreams/16294ebb-ec64-457e-bed2-d9781000fbfa/download File MD5 dba6d31b0e6d5570a88c35ad90e8f8cc 169565 text/plain THOM_MARK_PHD_2017.pdf.txt