Approximation Algorithms for the Submodular Load Balancing with Submodular Penalties

Xiaofei Liu, Peiyin Xing and Weidong Li
Additional contact information
Xiaofei Liu: School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China
Peiyin Xing: School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China
Weidong Li: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China

Mathematics, 2020, vol. 8, issue 10, 1-12

Abstract: In this paper, we study the submodular load balancing problem with submodular penalties. The objective of this problem is to balance the load among sets, while some elements can be rejected by paying some penalties. Officially, given an element set V , we want to find a subset R of rejected elements, and assign other elements to one of m sets A 1 , A 2 , ? , A m . The objective is to minimize the sum of the maximum load among A 1 , A 2 , ? , A m and the rejection penalty of R , where the load and rejection penalty are determined by different submodular functions. We study the submodular load balancing problem with submodular penalties under two settings: heterogenous setting (load functions are not identical) and homogenous setting (load functions are identical). Moreover, we design a Lovász rounding algorithm achieving a worst-case guarantee of m + 1 under the heterogenous setting and a min { m , ⌈ n m ⌉ + 1 } = O ( n ) -approximation combinatorial algorithm under the homogenous setting.

Keywords: load balancing; submodular function; submodular penalties; approximation algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/10/1785/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/10/1785/ (text/html)

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:gam:jmathe:v:8:y:2020:i:10:p:1785-:d:428414

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().