Approximation Algorithms for the Submodular Load Balancing with Submodular Penalties
Open Access
- 15 October 2020
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 8 (10) , 1785
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 . The objective is to minimize the sum of the maximum load among 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 under the heterogenous setting and a -approximation combinatorial algorithm under the homogenous setting.
Keywords
Funding Information
- National Natural Science Foundation of China (61662088)
This publication has 29 references indexed in Scilit:
- A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular PenaltiesAlgorithmica, 2011
- Submodular Approximation: Sampling-based Algorithms and Lower BoundsSIAM Journal on Computing, 2011
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral VariablesSIAM Journal on Discrete Mathematics, 2010
- A push-relabel framework for submodular function minimization and applications to parametric optimizationDiscrete Applied Mathematics, 2003
- Multiprocessor Scheduling with RejectionSIAM Journal on Discrete Mathematics, 2000
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- Using dual approximation algorithms for scheduling problems theoretical and practical resultsJournal of the ACM, 1987
- Exact and Approximate Algorithms for Scheduling Nonidentical ProcessorsJournal of the ACM, 1976
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966