.png){kind=icon}
.png){kind=icon}
Return
Incremental-Decremental Maximization
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-06706-7_7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We introduce a framework for incremental-decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized and a deterministic algorithm that both find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimum solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions, and gross substitute functions. Our results exhibit that incremental-decremental maximization is substantially more difficult than incremental maximization.
Keywords:
Incremental-decremental maximization
Submodular functions
Competitive algorithms
Bounded curvature
Gross substitutes
Journal
A
IF:
0
Papers:
15
Citations:
0