Online set multicover algorithms for dynamic D2D communications

Alan Kuhnle (), Xiang Li (), J. David Smith () and My T. Thai ()
Additional contact information
Alan Kuhnle: University of Florida
Xiang Li: University of Florida
J. David Smith: University of Florida
My T. Thai: Ton Duc Thang University

Journal of Combinatorial Optimization, 2017, vol. 34, issue 4, No 16, 1237-1264

Abstract: Abstract Motivated by the dynamic resource allocation problem for device-to-device (D2D) communications, we study the online set multicover problem (OSMC). In the online set multicover, the set X of elements to be covered is unknown in advance; furthermore, the coverage requirement of each element $$x \in X$$ x ∈ X is initially unknown. Elements of X together with coverage requirements are presented one at a time in an online fashion; and a feasible solution must be maintained at all times. We provide the first deterministic, online algorithms for OSMC with competitive ratios. We consider two versions of OSMC; in the first, each set may be picked only once, while the second version allows each set to be picked multiple times. For both versions, we present the first deterministic, online algorithms, with competitive ratios $$O( \log n \log m )$$ O ( log n log m ) and $$O( \log n (\log m + \log k) )$$ O ( log n ( log m + log k ) ) , repectively, where n is the number of elements, m is the number of sets, and k is the maximum coverage requirement. By simulation, we show the efficacy of these algorithms for resource allocation in the D2D setting by analyzing network throughput and other metrics, obtaining a large improvement in running time over offline methods.

Keywords: Online algorithm; Set multicover; Optimization; D2D communications; Resource allocation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0144-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:4:d:10.1007_s10878-017-0144-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0144-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().