Incremental Maximization for a Broad Class of Objectives

Disser, Yann; Weckbecker, David

doi:10.4230/LIPIcs.ESA.2025.92

Incremental Maximization
for a Broad Class of Objectives

Yann Disser

TU Darmstadt, Germany David Weckbecker

TU Darmstadt, Germany

Abstract

We consider incremental maximization problems, where the solution has to be built up gradually by adding elements one after the other. In every step, the incremental solution must be competitive, compared against the optimum solution of the current cardinality. We prove that a competitive solution always exists when the objective function is monotone and $\beta$ -accountable, by providing a scaling algorithm that guarantees a constant competitive ratio. This generalizes known results and, importantly, yields the first competitive algorithm for the natural class of monotone and subadditive objective functions.

Keywords and phrases:

incremental maximization, competitive analysis, subadditive functions

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Online algorithms ; Mathematics of computing

\rightarrow

Combinatorial algorithms ; Mathematics of computing

\rightarrow

Combinatorial optimization

Funding:

Supported by DFG grant DI 2041/2.

DOI:

10.4230/LIPIcs.ESA.2025.92

Event:

33rd Annual European Symposium on Algorithms (ESA 2025)

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Large infrastructure projects are typically implemented sequentially over longer periods of time. In such settings, it makes sense to prioritize completion of parts of the project that already yield some benefit on their own. This raises the general question of how to compute incremental solutions with a good partial benefit throughout the course of the project. We model such settings mathematically by using the abstract framework of the incremental maximization (IncMax) problem.

In the IncMax problem, we are given a countable set of elements $U$ , along with an objective function $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ . We generally require $f$ to be monotone, i.e., that $f(A)\leq f(B)$ for all $A\subseteq B\subseteq U$ . An incremental solution $\pi$ is a permutation $(e_{1},e_{2},\dots)$ of the elements in $U$ that specifies the order in which the elements are to be included in the solution. The solution after step $C\in\mathbb{N}$ is then given by $\pi(C):=\{e_{1},\dots,e_{C}\}$ , and we denote the optimum solution value of cardinality $C$ by

\textsc{Opt}(C):=\sup\{f(A)\mid A\subseteq U,|A|=C\}.

We say that the incremental solution $\pi$ is $\rho$ -competitive if $\textsc{Opt}(C)\leq\rho\cdot\pi(C)$ for all $C\in\mathbb{N}$ . The competitive ratio of $\pi$ is $\rho(\pi):=\inf\{\rho\geq 1\mid\pi\textrm{ is }\rho\textrm{-competitive}\}$ , the competitive ratio of a problem instance given by $U$ and $f$ is $\rho(U,f):=\inf_{\pi}\rho(\pi)$ , and the competitive ratio of a set of instances $\mathcal{C}$ is $\rho(\mathcal{C}):=\sup\{\rho(U,f)\mid(U,f)\in\mathcal{C}\}$ .

Clearly, we cannot hope for good incremental solutions in full generality: For example, if $f(E)$ is given by the value of a maximum flow using an edge set $E$ in some underlying graph that consists of a short path of low capacity and a long path of high capacity, then we have to decide whether to invest in the short path to obtain some value early, or in the long path to achieve a high value as quickly as possible, but cannot ensure both simultaneously. More generally, we must demand that the objective function has some form of a diminishing-returns property that requires the value of solutions to be explainable by the value of their parts, i.e., value cannot suddenly emerge upon completion of certain structures (such as paths in the flow example).

Diminishing returns are typically captured by submodular objective functions, i.e., functions $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ with $f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$ for all $A,B\subseteq U$ . In a classical result, Nemhauser et al. [25] showed that the obvious greedy algorithm, that adds to the current solution $S$ the element $e$ of largest marginal value $f(S\cup\{e\})-f(S)$ in each step, produces a $\frac{\mathrm{e}}{\mathrm{e}-1}$ -competitive solution for submodular objectives. The most natural relaxation of submodularity that still intuitively captures diminishing returns is subadditivity, i.e., $f(A)+f(B)\geq f(A\cup B)$ for all $A,B\subseteq U$ . While subadditivity is a classical and natural property that intuitively seems promising for incremental maximization, no bounds on the compatitive ratio were known to date.

Unable to bound the competitive ratio for subadditive objectives, Bernstein et al. [1] considered accountable functions $f$ instead (see Figure 1 along with the following). A function $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ is called accountable if, for every finite and non-empty set $S\subseteq U$ , there exists $e\in S$ with $f(S\setminus\{e\})\geq\bigl(1-\frac{1}{|S|}\bigr)f(S)$ . Intuitively, this property directly requires that the value of a set cannot suddenly emerge when adding its last element. Bernstein et al. [1] gave a $(\varphi+1)$ -competitive scaling algorithm for accountable objectives, where $\varphi:=(\sqrt{5}+1)/2$ denotes the golden ratio.

Note that submodular functions are accountable, and many combinatorial maximization problems, such as weighted (multidimensional) matching, set packing, coverage, knapsack, and many more, give rise to accountable objective functions (see [1]). On the other hand, not all subadditive functions are accountable. For a simple example, assume that the elements of $U$ represent identical unit squares, and $f(S)$ is the diameter of the largest square that can be tiled with the elements in $S\subseteq U$ . Then, $f(S)=\lfloor\sqrt{|S|}\rfloor$ grows strictly sublinearly in $|S|$ and is thus subadditive, but it is not accountable, as can be seen by considering $|S|=4$ , which yields $f(S\setminus\{e\})=1<\frac{3}{2}=\bigl(1-\frac{1}{4})f(S)$ for all $e\in S$ . More generally, functions of the form $f(A)=\lfloor g(|A|)\rfloor$ with $g\in o(|A|)$ are subadditive, but not accountable.

Disser and Weckbecker [11] considered $\gamma$ - $\alpha$ -augmentability as an alternative relaxation of submodularity that additionally maintains competitiveness of the greedy algorithm. A function is called $\gamma$ - $\alpha$ -augmentable if, for all finite $A,B\subseteq U$ , there exists $b\in B$ with $f(A\cup\{b\})-f(A)\geq\frac{\gamma f(A\cup B)-\alpha f(A)}{|B|}$ . In this setting, the greedy algorithm has competitive ratio exactly $\frac{\alpha}{\gamma}\cdot\frac{\mathrm{e}^{\alpha}}{\mathrm{e}^{\alpha}-1}$ .

In this paper, we provide a scaling algorithm that is competitive for an abstract class of functions that relaxes all above classes and includes, for the first time, all subadditive functions.

Figure 1: Relation of different function properties, including fractionally subadditivity (FSA), weighted rank functions (WRF), and functions of bounded submodularity ratio (BSR). For the depicted inclusions to hold simultaneously, we can set

\beta=\min\{\frac{1}{2},\frac{\gamma}{\alpha}\}

.

Our results

We introduce a class of functions based on an equivalent characterization of accountability given by Disser et al. [10]. They showed that a function $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ is accountable if and only if, for every finite $S\subseteq U$ , there exists an ordering $(e_{1},\dots,e_{|S|})$ of $S$ with $f(\{e_{1},\dots,e_{i}\})\geq\frac{i}{|S|}f(S)$ for all $i\in\{1,\dots,|S|\}$ . We relax this characterization as follows.

Definition 1.

For $\beta\in(0,1]$ , a function $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ is called $\beta$ -accountable if, for every $S\subseteq U$ , there exists an ordering $(e_{1},\dots,e_{|S|})$ of the elements in $S$ such that, for all $i\in\{1,\dots,|S|\}$ ,

f(\{e_{1},\dots,e_{i}\})\geq\beta\frac{i}{|S|}f(S).

This definition generalizes multiple other function properties (see Figure 1). In particular, accountable functions [10] correspond exactly to $1$ -accountable functions (by definition and [10]), every (monotone) $\gamma$ - $\alpha$ -augmentable function [11] is $\frac{\gamma}{\alpha}$ -accountable (Proposition 12), and every (monotone) subadditive function is $\frac{1}{2}$ -accountable (Proposition 8).

We establish a general upper bound on the competitive ratio of incremental maximization with $\beta$ -accountable objective via a scaling algorithm parameterized in $\beta$ , and complement this result by a lower bound that is tight in the limit $\beta\to 0$ (see Figure 2).

Theorem 2.

IncMax with a $\beta$ -accountable objective has competitive ratio

\rho\in\left[\frac{1}{\beta}\cdot\biggl(1+\frac{1}{\bigl\lceil\frac{1}{\beta}% \bigr\rceil+1}\biggr),\frac{1}{2\beta}+1+\sqrt{\frac{1}{4\beta^{2}}+1}\right].

Note that, for $\beta=1$ , the upper bound recovers the bound of $\varphi+1\approx 2.618$ of [1].

Importantly, Theorem 2 yields the first constant upper bound for the natural class of subadditive objective functions ( $\beta=\frac{1}{2}$ ).

Theorem 3.

IncMax with a subadditive objective has competitive ratio at most $2+\sqrt{2}$ .

Furthermore, Theorem 2 also yields the following bound, which improves on the best known upper bound for $\gamma$ - $\alpha$ -augmentable functions of [11] when $\gamma<\alpha\frac{\mathrm{e}^{\alpha}}{\mathrm{e}^{\alpha}-1}$ .

Theorem 4.

IncMax with a $\gamma$ - $\alpha$ -augmentable objective has competitive ratio at most

\frac{\alpha}{2\gamma}+1+\sqrt{\frac{\alpha^{2}}{4\gamma^{2}}+1}.

Figure 2: Plot of the bounds of Theorem 2, and their difference (red).

Related work

The general framework of incremental maximization was first proposed by Bernstein et al. [1]. They assumed that the objective is accountable and showed that in this case the competitive ratio of this problem is at most $\varphi+1\approx 2.618$ . Utilizing a continuization technique, Disser et al. [10] showed a lower bound of $2.246$ in this setting and provided evidence that the upper bound of $\varphi+1$ is tight. Before the general framework was introduced, Zhu et al. [30] considered a special case of the problem where edges have to be added over time in order to maximize the number of internal nodes. They proved an upper bound of $12/7$ .

The performance of a simple greedy algorithm for this problem was investigated separately. Rado [27] showed that the greedy algorithm performs optimally if the objective function is modular. For submodular objectives, Nemhauser et al. [25] showed that the greedy algorithm has a competitive ratio of at most $\frac{\mathrm{e}}{\mathrm{e}-1}$ . This is known to be tight due to Feige [12]. More recently, other classes of objectives were considered. Das and Kempe [6] introduced the submodularity ratio as a relaxation of submodularity and showed that the greedy algorithm has a competitive ratio of at most $\frac{\mathrm{e}^{\gamma}}{\mathrm{e}^{\gamma}-1}$ for objectives with submodularity ratio $\gamma\in[0,1]$ . This was later shown to be tight by Bian et al. [2] who also parametrized the bound by the curvature. A different relaxation of submodularity is $\alpha$ -augmentability. Here, the competitive ratio of the greedy algorithm is known to be at most $\frac{\mathrm{e}^{\alpha}}{\mathrm{e}^{\alpha}-1}$ due to Bernstein et al. [1]. Disser and Weckbecker [11] showed that this upper bound is tight and generalized this result by showing that the greedy algorithm has a competitive ratio of exactly $\frac{\alpha}{\gamma}\cdot\frac{\mathrm{e}^{\alpha}}{\mathrm{e}^{\alpha}-1}$ if the objective is $\gamma$ - $\alpha$ -augmentable.

A generalization of the incremental maximization is the problem where, instead of an increasing cardinality constraint, one is faced with an increasing knapsack constraint. Under the assumption that the objective is modular, Megow and Mestre [22] provide an instance-sensitive near-optimal solution. Disser et al. [9] additionally assume that items that do not fit into the knapsack can be discarded and show that the competitive ratio in this setting is exactly $2$ . This result was later generalized to submodular objectives with a bounded curvature by Klimm and Knaack [20]. Kawase et al. [19] gave an upper bound of $\frac{2\mathrm{e}}{\mathrm{e}-1}$ on the randomized competitive ratio of the incremental maximization problem under a knapsack constraint with submodular objective under the assumption that items that do not fit can be discarded. Instead of discarding items that do not fit, Navarra and Pinotti [24] assumed that every item fits into the knapsack and provided a $2$ -competitive algorithm for modular objectives. Disser et al. [8] assumed that the ratio between the largest and smallest value of a single element is bounded by some constant $M$ and showed that the competitive ratio of the incremental maximization problem under a knapsack constraint with a fractionally subadditive objective lies between $\max\{2.618,M\}$ and $\max\{3.293\sqrt{M},2M\}$ .

Disser et al. [7] considered an incremental budget constraint for the prize-collecting Steiner tree problem, where the objective does not obey a diminishing returns property and the authors had to resort to bicriterial approximation guarantees. Other variants of the incremental maximization problem include a variation where the goal is to maximize a sum-objective [18, 14, 29], or incremental solutions in a changing environment [16, 17, 28]. Incremental minimization considered, among others, for the $k$ -center problem [15], the minimum latency problem [3, 13, 4], the $k$ -median problem [23, 5, 21], and the facility location problem [26, 21].

2 Competitive Bounds

The best known algorithm to solve the IncMax problem with an accountable objective was presented in [1]. It follows the idea of calculating cardinalities $c_{0},c_{1},\dots$ and adding the optimum solution sets for these cardinalities one after the other, where the order of the elements within each set follows Definition 1. The cardinalities $c_{0},c_{1},\dots$ are calculated by setting $c_{0}=1$ and iteratively scaling via $c_{i+1}=\lceil\delta c_{i}\rceil$ for some $\delta>1$ .

Since $\beta$ -accountability is closely related to accountability, we introduce a modified version of this algorithm to find an incremental solution for the IncMax problem with a $\beta$ -accountable objective.

The algorithm $\textsc{Scaling}_{\beta}$ uses the scaling parameter

\delta=\frac{1}{2\beta}+1+\sqrt{\frac{1}{4\beta^{2}}+1}

and chooses

c_{1}\in{\arg\max}_{C\in\mathbb{N}}\frac{\textsc{Opt}(C)}{C}

in an arbitrary, but fixed way. Then, for $i\in\mathbb{N}$ , it chooses

c_{i+1}\in{\arg\max}_{C\in\mathbb{N},C\geq\delta c_{i}}\frac{\textsc{Opt}(C)}{% C},

also in an arbitrary, but fixed way. $\textsc{Scaling}_{\beta}$ operates in phases, and in phase $i\in\mathbb{N}$ , it adds the optimum solution of cardinality $c_{i}$ in the order given by Definition 1.

We state the following observation.

Observation 5.

For all $i\in\mathbb{N}$ , we have

(i)

$c_{i+1}\geq\delta c_{i}$ ,
(ii)

$\sum_{j=1}^{i}c_{j}\leq\frac{\delta}{\delta-1}c_{i}$ ,
(iii)

$\frac{\textsc{Opt}(c_{i})}{c_{i}}\geq\frac{\textsc{Opt}(c)}{c}$ for all $c\in\mathbb{N}_{\geq\delta c_{i}}$ .

Proof.

$(i)$ and $(iii)$ follow immediately from the definition of $c_{i}$ for all $i\in\mathbb{N}$ .

Furthermore, we have

\sum_{j=1}^{i}c_{j}\overset{(i)}{\leq}\sum_{j=1}^{i}\Bigl(\frac{1}{\delta}% \Bigr)^{i-j}c_{i}\leq\sum_{j=1}^{\infty}\Bigl(\frac{1}{\delta}\Bigr)^{i-j}c_{i% }=\frac{\delta}{\delta-1}c_{i}.

$\hfill\blacktriangleleft$

We are now ready to prove an upper bound on the competitive ratio of $\textsc{Scaling}_{\beta}$ .

Theorem 6.

The algorithm $\textsc{Scaling}_{\beta}$ is $\delta$ -competitive for IncMax with a $\beta$ -accountable objective function.

Proof.

Let $\pi$ denote the incremental solution of $\textsc{Scaling}_{\beta}$ . Let $C\in\mathbb{N}$ and $i\in\mathbb{N}$ such that $C\in\bigl(\sum_{j=1}^{i-1}c_{j},\sum_{j=1}^{i}c_{j}\bigr]$ . If $i=1$ , we let $x=0$ , otherwise, let

x=\frac{1}{\beta}\cdot\frac{\textsc{Opt}(c_{i-1})}{\textsc{Opt}(c_{i})}c_{i}+% \sum_{j=1}^{i-1}c_{j},

(1)

i.e., we have

\textsc{Opt}(c_{i-1})=\beta\frac{x-\sum_{j=1}^{i-1}c_{j}}{c_{i}}\textsc{Opt}(c% _{i}).

The value $x$ is chosen such that, if $C\geq x$ , then the value of the partially added optimum solution of cardinality $c_{i}$ in the solution $\pi(C)$ is at least as large as the value of the completely contained optimum solution of cardinality $c_{i-1}$ .

Case 1: $C<\lceil\delta c_{i-1}\rceil$ .

As $\pi(C)$ contains the optimum solution of cardinality $c_{i-1}$ , by monotonicity, we have

\frac{\textsc{Opt}(C)}{f(\pi(C))}\leq\frac{\textsc{Opt}(C)}{\textsc{Opt}(c_{i-% 1})}\leq\frac{\textsc{Opt}(\lceil\delta c_{i-1}\rceil-1)}{\textsc{Opt}(c_{i-1}% )}\overset{\textrm{Obs. \ref{obs:betaAcc_betaScaling_observations} }(iii)}{% \leq}\frac{\lceil\delta c_{i-1}\rceil-1}{c_{i-1}}\leq\delta.

Case 2: $\lceil\delta c_{i-1}\rceil\leq C<x$ .

Note that $C<x$ implies that $x>0$ , i.e., (1) holds. The solution $\pi(C)$ contains the optimum solution of cardinality $c_{i-1}$ . Thus,

$\displaystyle\frac{\textsc{Opt}(C)}{f(\pi(C))}$	$\displaystyle\leq$	$\displaystyle\frac{\textsc{Opt}(C)}{\textsc{Opt}(c_{i-1})}$
	$\displaystyle\overset{\textrm{Obs. \ref{obs:betaAcc_betaScaling_observations} % }(iii)}{\leq}$	$\displaystyle\frac{\textsc{Opt}(c_{i})}{\textsc{Opt}(c_{i-1})}\cdot\frac{C}{c_% {i}}$
	$\displaystyle\leq$	$\displaystyle\frac{\textsc{Opt}(c_{i})}{\textsc{Opt}(c_{i-1})}\cdot\frac{x}{c_% {i}}$
	$\displaystyle\overset{\eqref{eq:betaAcc_equality_for_x}}{=}$	$\displaystyle\frac{1}{\beta}+\frac{\textsc{Opt}(c_{i})}{\textsc{Opt}(c_{i-1})}% \cdot\frac{1}{c_{i}}\sum_{j=1}^{i-1}c_{j}$
	$\displaystyle\overset{\textrm{Obs.\nobreak\ \ref{obs:betaAcc_betaScaling_% observations} }(iii)}{\leq}$	$\displaystyle\frac{1}{\beta}+\frac{c_{i}}{c_{i-1}}\cdot\frac{1}{c_{i}}\sum_{j=% 1}^{i-1}c_{j}$
	$\displaystyle\overset{\textrm{Obs.\nobreak\ \ref{obs:betaAcc_betaScaling_% observations} }(ii)}{\leq}$	$\displaystyle\frac{1}{\beta}+\frac{\delta}{\delta-1}=\delta,$

where the last equality follows from the definition of $\delta$ .

Case 3: $C\geq\lceil\delta c_{i-1}\rceil$ , $C\geq x$ .

If $i=1$ , by definition of $c_{1}$ , we have

\frac{\textsc{Opt}(C)}{f(\pi(C))}\leq\frac{\textsc{Opt}(C)}{\beta\frac{C}{c_{1% }}\textsc{Opt}(c_{1})}\leq\frac{1}{\beta}<\delta.

Now, assume that $i\geq 2$ , i.e., (1) holds. The solution $\pi(C)$ contains $C-\sum_{j=1}^{i-1}c_{j}$ elements from the optimum solution of cardinality $c_{i}$ . Thus,

$\displaystyle\frac{\textsc{Opt}(C)}{f(\pi(C))}$	$\displaystyle\leq$	$\displaystyle\frac{\textsc{Opt}(C)}{\beta\frac{C-\sum_{j=1}^{i-1}c_{j}}{c_{i}}% \textsc{Opt}(c_{i})}$
	$\displaystyle\overset{\textrm{Obs.\nobreak\ \ref{obs:betaAcc_betaScaling_% observations} }(iii)}{\leq}$	$\displaystyle\frac{1}{\beta}\cdot\frac{C}{C-\sum_{j=1}^{i-1}c_{j}}$
	$\displaystyle\overset{C\geq x}{\leq}$	$\displaystyle\frac{1}{\beta}\cdot\frac{x}{x-\sum_{j=1}^{i-1}c_{j}}$
	$\displaystyle\overset{\eqref{eq:betaAcc_equality_for_x}}{=}$	$\displaystyle\frac{1}{\beta}\Biggl(1+\frac{\sum_{j=1}^{i-1}c_{j}}{\frac{1}{% \beta}\cdot\frac{\textsc{Opt}(c_{i-1})}{\textsc{Opt}(c_{i})}c_{i}}\Biggr)$
	$\displaystyle=$	$\displaystyle\frac{1}{\beta}+\frac{\textsc{Opt}(c_{i})}{\textsc{Opt}(c_{i-1})}% \cdot\frac{1}{c_{i}}\sum_{j=1}^{i-1}c_{j}$
	$\displaystyle\overset{\textrm{Obs.\nobreak\ \ref{obs:betaAcc_betaScaling_% observations} }(iii)}{\leq}$	$\displaystyle\frac{1}{\beta}+\frac{c_{i}}{c_{i-1}}\cdot\frac{1}{c_{i}}\sum_{j=% 1}^{i-1}c_{j}$
	$\displaystyle\overset{\textrm{Obs.\nobreak\ \ref{obs:betaAcc_betaScaling_% observations} }(ii)}{\leq}$	$\displaystyle\frac{1}{\beta}+\frac{\delta}{\delta-1}$
	$\displaystyle=$	$\displaystyle\delta.\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad% \qquad\qquad\qquad\qquad\$

$\hfill\blacktriangleleft$

We complement this upper bound with a lower bound, that, in particular, shows that for $\beta\rightarrow 0$ , we cannot be better than $\frac{1}{\beta}$ -competitive.

Theorem 7.

For all $\beta\in(0,1]$ , the competitive ratio of IncMax with a $\beta$ -accountable objective function is at least

\frac{1}{\beta}\cdot\biggl(1+\frac{1}{\bigl\lceil\frac{1}{\beta}\bigr\rceil+1}% \biggr).

Proof.

Let $k:=\lceil\frac{1}{\beta}\rceil+2$ and $d:=\frac{k-1}{k}\beta$ . We define an instance where no incremental solution can have a competitive ratio better than $\frac{1}{d}$ . Let $U=\{e_{1},\dots,e_{k+1}\}$ be the groundset and $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ be the objective such that, for $S\subseteq U$ ,

f(S)=\begin{cases}\frac{kd}{\beta}=k-1,&\textrm{if }\{e_{2},\dots,e_{k+1}\}% \subseteq S,\\ \max\bigl\{|\{e_{1}\}\cap S|,|\{e_{2},\dots,e_{k+1}\}\cap S|\cdot d\bigr\},&% \textrm{else.}\end{cases}

This objective is monotone because of the maximum in the definition and because $\frac{kd}{\beta}\geq kd$ . We show that $f$ is $\beta$ -accountable. For this, let $S\subseteq U$ . We have to show that there is an ordering $\bigl(e_{i_{1}},\dots,e_{i_{|S|}}\bigr)$ of the elements in $S$ such that $f(\{e_{i_{1}},\dots,e_{i_{j}}\})\geq\beta\frac{j}{|S|}f(S)$ for all $j\in\{1,\dots,|S|\}$ . If we have $e_{1}\in S$ and $f(S)=1$ , we can simply choose $e_{1}$ to be the first element in the ordering and obtain

f(\{e_{i_{1}},\dots,e_{i_{j}}\})=1=f(S)\geq\beta\frac{j}{|S|}f(S)

for all $j\in\{1,\dots,|S|\}$ . Otherwise, if $e_{1}\notin S$ or $f(S)>1$ , then, with $S^{\prime}:=S\cap\{e_{2},\dots,e_{k+1}\}$ , either $f(S)=\frac{kd}{\beta}=\frac{|S^{\prime}|d}{\beta}$ , or $f(S)=|S^{\prime}|d\leq\frac{|S^{\prime}|d}{\beta}$ . In our ordering, we can put the elements from $S^{\prime}$ in the beginning and, for $j\in\{1,\dots,|S^{\prime}|\}$ , obtain

f(\{e_{i_{1}},\dots,e_{i_{j}}\})\geq j\cdot d=\beta\frac{j}{|S^{\prime}|}\frac% {|S^{\prime}|d}{\beta}\geq\beta\frac{j}{|S^{\prime}|}f(S)\geq\beta\frac{j}{|S|% }f(S).

If $S^{\prime}=S$ , we are done. Otherwise, $|S|=|S^{\prime}|+1$ holds and, for $j=|S|$ , we have $f(\{e_{i_{1}},\dots,e_{i_{j}}\})=f(S)\geq\beta\frac{j}{|S|}f(S)$ .

Let $\pi$ be an incremental solution for this instance. We consider two cases. First, assume that $e_{1}$ is not the last element in the ordering $\pi$ . We have

(k-1)d=\frac{\bigl(\bigl\lceil\frac{1}{\beta}\bigr\rceil+1\bigr)^{2}}{\bigl% \lceil\frac{1}{\beta}\bigr\rceil+2}\beta>\frac{\bigl\lceil\frac{1}{\beta}\bigr% \rceil^{2}+2\bigl\lceil\frac{1}{\beta}\bigr\rceil}{\bigl\lceil\frac{1}{\beta}% \bigr\rceil+2}\beta=\biggl\lceil\frac{1}{\beta}\biggr\rceil\beta\geq 1.

The solution $\pi(k)$ contains $e_{1}$ and $k-1$ elements from $\{e_{2},\dots,e_{k+1}\}$ . Thus,

f(\pi(k))=\max\{1,(k-1)d\}=(k-1)d.

The optimum solution of cardinality $k$ is the set $\{e_{2},\dots,e_{k+1}\}$ with a value of $k-1$ . Thus, in this case, the competitive ratio of $\pi$ is at least $\frac{1}{d}$ .

Now, consider the other case, i.e., $e_{1}$ is the last element in the ordering $\pi$ . Then the solution $\pi(1)$ contains exactly one element from the set $\{e_{2},\dots,e_{k+1}\}$ and has therefore value $f(\pi(1))=d$ . The optimum solution of cardinality $1$ is $\{e_{1}\}$ with a value of $1$ . Thus, also in this case, the competitive ratio of $\pi$ is at least $\frac{1}{d}$ . $\hfill\blacktriangleleft$

In Figure 2, we plot the upper bound from Theorem 6 and the lower bound from Theorem 7 in black, as well as a plot of their difference in red. On the one hand, one can see that both bounds are unbounded for $\beta\rightarrow 0$ . This seems plausible because for $\beta\rightarrow 0$ , we have (almost) no guarantee that the value of large sets is bounded by the value of smaller sets. On the other hand, one can see in Figure 2 that the difference between upper and lower bound is almost $0$ for $\beta\rightarrow 0$ . Thus, in the limit $\beta\rightarrow 0$ , $\textsc{Scaling}_{\beta}$ performs optimally.

3 Incremental Maximization for Subclasses

We employ the previous result to obtain new and improved bounds on the competitive ratio of IncMax with subadditive and $\gamma$ - $\alpha$ -augmentable objectives.

3.1 Subadditivity

In order to derive results for IncMax with subadditive objectives, we compare $\beta$ -accountability and subadditivity.

Proposition 8.

Every monotone, subadditive function is $\frac{1}{2}$ -accountable.

Proof.

Let $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ be monotone and subadditive, $S\subseteq U$ be finite, and $k:=|S|$ . We define $\ell:=\lceil\log_{2}k\rceil$ , i.e., we have $2^{\ell-1}<k\leq 2^{\ell}$ . Furthermore, we define $S_{\ell}:=S$ and iteratively, for $j\in\{\ell-1,\dots,0\}$ , $S_{j}\subseteq S_{j+1}$ with $|S_{j}|=\bigl\lceil\frac{k}{2^{\ell-j}}\bigr\rceil$ and $f(S_{j})\geq\frac{1}{2}f(S_{j+1})$ . This is possible as we will see now. We have $2\bigl\lceil\frac{k}{2^{\ell-j}}\bigr\rceil=\bigl\lceil 2\bigl\lceil\frac{k}{2% ^{\ell-j}}\bigr\rceil\bigr\rceil\geq\bigl\lceil\frac{k}{2^{\ell-j-1}}\bigr\rceil$ , i.e., we can choose $A,B\subseteq S_{j}$ with $|A|=|B|=\bigl\lceil\frac{k}{2^{\ell-j}}\bigr\rceil$ and $A\cup B=S_{j+1}$ . By subadditivity, we have $f(A)\geq\frac{1}{2}f(S_{j+1})$ or $f(B)\geq\frac{1}{2}f(S_{j+1})$ . Thus, we can choose $S_{j}\in\{A,B\}$ with the desired properties.

Now, consider any order $(e_{1},\dots,e_{k})$ of $S$ with $\{e_{1},\dots,e_{|S_{j}|}\}=S_{j}$ for all $j\in\{0,\dots,\ell\}$ . Let $i\in\{1,\dots,k\}$ and $j\in\{0,\dots,\ell\}$ such that $\bigl\lceil\frac{k}{2^{\ell-j}}\bigr\rceil\leq i<\bigl\lceil\frac{k}{2^{\ell-j% -1}}\bigr\rceil$ . This implies that $S_{j}\subseteq\{e_{1},\dots,e_{i}\}$ and, because $i\in\mathbb{N}$ , that $i<\frac{k}{2^{\ell-j-1}}$ . Together with monotonicity of $f$ , we obtain

f(\{e_{1},\dots,e_{i}\})\geq f(S_{j})\geq\biggl(\frac{1}{2}\biggr)^{\ell-j}f(S% _{\ell})=\frac{1}{2^{\ell-j}}f(S)\geq\frac{1}{2}\frac{i}{k}f(S),

which yields $\frac{1}{2}$ -accountability. $\hfill\blacktriangleleft$

We combine Theorem 6 and Proposition 8 to obtain an upper bound on the competitive ratio of IncMax with a subadditive objective. This immediately proves Theorem 3.

Theorem 3. [Restated, see original statement.]

IncMax with a subadditive objective has competitive ratio at most $2+\sqrt{2}$ .

We complement this upper bound on the competitive ratio of IncMax with subadditive objective functions by a lower bound. To this end, we employ separability of problem instances of incremental maximization, a property introduced in [10].

Definition 9.

An instance of IncMax with objective $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ is called separable if there exist a partition $U=U_{1}\cup U_{2}\cup\dots$ of $U$ and densities $d_{i}>0$ such that, for all $S\subseteq U$ ,

f(S)=\max_{i\in\mathbb{N}}\{|S\cap U_{i}|\cdot d_{i}\}.

Proposition 10.

The objective function of every separable problem instance is subadditive.

Proof.

Let a separable instance with objective function $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ be given. Furthermore, let $U=U_{1}\cup U_{2}\cup\dots$ be a partition of $U$ , and let $d_{1},d_{2},\dots>0$ be the densities such that, for all $S\subseteq U$ ,

f(S)=\max_{i\in\mathbb{N}}|S\cap U_{i}|\cdot d_{i}.

In order to show subadditivity, we fix two sets $A,B\subseteq U$ . Let $i^{*}\in\mathbb{N}$ be the index such that $f(A\cup B)=|(A\cup B)\cap U_{i^{*}}|\cdot d_{i^{*}}$ . Then

	$\displaystyle f(A\cup B)$	$\displaystyle=\|(A\cup B)\cap U_{i^{}}\|\cdot d_{i^{}}$
		$\displaystyle=\|A\cap U_{i^{}}\|\cdot d_{i^{}}+\|(B\setminus A)\cap U_{i^{}}\|% \cdot d_{i^{}}$
		$\displaystyle\leq\|A\cap U_{i^{}}\|\cdot d_{i^{}}+\|B\cap U_{i^{}}\|\cdot d_{i^% {}}$
		$\displaystyle\leq\bigl(\max_{i\in\mathbb{N}}\|A\cap U_{i}\|\cdot d_{i}\bigr)+% \bigl(\max_{i\in\mathbb{N}}\|B\cap U_{i}\|\cdot d_{i}\bigr)$
		$\displaystyle=f(A)+f(B).\$

$\hfill\blacktriangleleft$

This result yields that the (non-strict) competitive ratio of IncMax with subadditive objectives is at least that for separable instances. In [10], the authors show a lower bound of $2.246$ on the competitive ratio in the separable setting. Thus, we obtain the following.

Corollary 11.

The competitive ratio of IncMax with a subadditive objective function is at least $2.246$ .

This bound is weaker than the lower bound of $\frac{8}{3}$ from Theorem 7 for IncMax with a $\frac{1}{2}$ -accountable objective. Yet, note that the lower bound construction in the proof of Theorem 7 is not subadditive.

3.2 $\gamma$ - $\alpha$ -Augmentability

We now turn to comparing $\beta$ -accountability and $\gamma$ - $\alpha$ -augmentability.

Proposition 12.

For all $\gamma\in(0,1]$ and $\alpha\geq 1$ , every monotone, $\gamma$ - $\alpha$ -augmentable function is $\frac{\gamma}{\alpha}$ -accountable.

Proof.

For $\gamma\in(0,1]$ and $\alpha\geq 1$ , let $f\colon 2^{U}\rightarrow\mathbb{R}_{\geq 0}$ be monotone and $\gamma$ - $\alpha$ -augmentable. Let $S\subseteq U$ be finite and $k:=|S|$ . By $\gamma$ - $\alpha$ -augmentability, there exists an ordering $(e_{1},\dots,e_{k})$ of the elements in $S$ such that, for all $i\in\{0,\dots,k-1\}$ ,

f(\{e_{1},\dots,e_{i+1}\})-f(\{e_{1},\dots,e_{i}\})\geq\frac{\gamma f(S)-% \alpha f(\{e_{1},\dots,e_{i}\})}{k-i}.

For $i\in\{0,\dots,k\}$ , let $S_{i}:=\{e_{1},\dots,e_{i}\}$ . Then, for $i\in\{0,\dots,k-1\}$ , this yields

f(S_{i+1})-f(S_{i})\geq\alpha\frac{\frac{\gamma}{\alpha}f(S)-f(S_{i})}{k-i}% \overset{\alpha\geq 1}{\geq}\frac{\frac{\gamma}{\alpha}f(S)-f(S_{i})}{k-i}.

(2)

To show $\frac{\gamma}{\alpha}$ -accountability of $f$ , we prove by induction that, for $i\in\{1,\dots,k\}$ , we have

f(S_{i})\geq\frac{\gamma}{\alpha}\frac{i}{k}f(S).

(3)

For $i=0$ , (2) yields

f(S_{1})\geq\frac{1}{k}\biggl(\frac{\gamma}{\alpha}f(S)-f(\emptyset)\biggr)+f(% \emptyset)=\frac{\gamma}{\alpha}\frac{1}{k}f(S)+\biggl(1-\frac{1}{k}\biggr)f(% \emptyset)\geq\frac{\gamma}{\alpha}\frac{1}{k}f(S),

where the last inequality follows from non-negativity of $f$ .

Now, suppose that (3) holds for some $i\in\{0,\dots,k-1\}$ . Then

$\displaystyle f(S_{i+1})$	$\displaystyle\overset{\eqref{eq:gam-alph-aug_implies_gam-alph-acc_2}}{\geq}$	$\displaystyle f(S_{i})+\frac{\frac{\gamma}{\alpha}f(S)-f(S_{i})}{k-i}$
	$\displaystyle=$	$\displaystyle\frac{\gamma}{\alpha}\frac{1}{k-i}f(S)+\biggl(1-\frac{1}{k-i}% \biggr)f(S_{i})$
	$\displaystyle\overset{\eqref{eq:gam-alph-aug_implies_gam-alph-acc_ind-hyp}}{\geq}$	$\displaystyle\frac{\gamma}{\alpha}\frac{1}{k-i}f(S)+\biggl(\frac{k-i-1}{k-i}% \biggr)\frac{\gamma}{\alpha}\frac{i}{k}f(S)$
	$\displaystyle=$	$\displaystyle\frac{\gamma}{\alpha}\frac{ki+k-i^{2}-i}{(k-i)k}f(S)$
	$\displaystyle=$	$\displaystyle\frac{\gamma}{\alpha}\frac{(k-i)(i+1)}{(k-i)k}f(S)$
	$\displaystyle=$	$\displaystyle\frac{\gamma}{\alpha}\frac{i+1}{k}f(S),$

which concludes the induction. $\hfill\blacktriangleleft$

We combine the results from Proposition 12 and Theorem 6 to obtain an upper bound on the competitive ratio of IncMax with a monotone and $\gamma$ - $\alpha$ -augmentable objective. This immediately proves Theorem 4.

Theorem 13.

For $\gamma\in(0,1]$ and $\alpha\geq 1$ , $\textsc{Scaling}_{\gamma/\alpha}$ has a competitive ratio of at most

\frac{\alpha}{2\gamma}+1+\sqrt{\frac{\alpha^{2}}{4\gamma^{2}}+1}

for IncMax with a $\gamma$ - $\alpha$ -augmentable objective.

We compare this upper bound on the competitive ratio of IncMax with a $\gamma$ - $\alpha$ -augmentable objective to

\frac{\alpha}{\gamma}\cdot\frac{\mathrm{e}^{\alpha}}{\mathrm{e}^{\alpha}-1},

the competitive ratio of the greedy algorithm for IncMax with $\gamma$ - $\alpha$ -augmentable objectives [11]. Let the ratio between the two upper bounds be denoted by

r(\gamma,\alpha):=\frac{\frac{\alpha}{2\gamma}+1+\sqrt{\frac{\alpha^{2}}{4% \gamma^{2}}+1}}{\frac{\alpha}{\gamma}\cdot\frac{\mathrm{e}^{\alpha}}{\mathrm{e% }^{\alpha}-1}}=\frac{\mathrm{e}^{\alpha}-1}{\mathrm{e}^{\alpha}}\cdot\Biggl(% \frac{1}{2}+\frac{\gamma}{\alpha}+\sqrt{\frac{1}{4}+\frac{\gamma^{2}}{\alpha^{% 2}}}\Biggr).

We have $\lim_{\gamma\rightarrow 0}r(\gamma,\alpha)=\frac{\mathrm{e}^{\alpha}-1}{% \mathrm{e}^{\alpha}}<1$ , i.e., for small values of $\gamma$ , $\textsc{Scaling}_{\gamma/\alpha}$ performs better than the greedy algorithm. Since $\gamma\in(0,1]$ and $\alpha\geq 1$ , we have $r(\gamma,\alpha)=1$ if and only if $\gamma=\alpha\frac{\mathrm{e}^{\alpha}}{\mathrm{e}^{2\alpha}-1}$ . This value lies in the interval $\bigl(0,\frac{\mathrm{e}}{\mathrm{e}^{2}-1}\bigr]\subseteq(0,0.426)$ , and for $\alpha\rightarrow\infty$ , approaches $0$ (cf. Figure 3). Thus, for large $\alpha\geq 1$ , the greedy algorithm performs better than $\textsc{Scaling}_{\gamma/\alpha}$ for almost all values of $\gamma\in(0,1]$ . This is probably due to the fact that $\gamma$ - $\alpha$ -augmentability is a property that relaxes an inequality that is a core estimate in the analysis of the the greedy algorithm for monotone and submodular functions.

Figure 3: Plot of the value of

\gamma

depending on

\alpha

for which

\textsc{Scaling}_{\gamma/\alpha}

and the greedy algorithm achieve the same competitive ratio. For values of

\gamma

below this line,

\textsc{Scaling}_{\gamma/\alpha}

performs better, and vice versa.

References

[1] Aaron Bernstein, Yann Disser, Martin Groß, and Sandra Himburg. General bounds for incremental maximization. Mathematical Programming, 191(2):953–979, 2022. doi:10.1007/s10107-020-01576-0.
[2] Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th Interantional Conference on Machine Learning (ICML), pages 498–507, 2017. URL: https://proceedings.mlr.press/v70/bian17a.html.
[3] Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. The minimum latency problem. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 163–171, 1994. doi:10.1145/195058.195125.
[4] Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. Paths, trees, and minimum latency tours. In 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 36–45, 2003. doi:10.1109/SFCS.2003.1238179.
[5] Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young. Incremental medians via online bidding. Algorithmica, 50(4):455–478, 2008. doi:10.1007/s00453-007-9005-x.
[6] Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19:1–34, 2018. URL: https://jmlr.org/papers/v19/16-534.html.
[7] Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial approximation for the incremental prize-collecting steiner-tree problem. In ESA 2024, pages 47:1–47:16, 2024. doi:10.4230/LIPIcs.ESA.2024.47.
[8] Yann Disser, Max Klimm, Annette Lutz, and David Weckbecker. Fractionally subadditive maximization under an incremental knapsack constraint. SIAM Journal on Discrete Mathematics, 38(1):764–789, 2024.
[9] Yann Disser, Max Klimm, Nicole Megow, and Sebastian Stiller. Packing a knapsack of unknown capacity. SIAM Journal on Discrete Mathematics, 31(3):1477–1497, 2017. doi:10.1137/16M1070049.
[10] Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker. Incremental maximization via continuization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261, pages 47:1–47:17, 2023. doi:10.4230/LIPIcs.ICALP.2023.47.
[11] Yann Disser and David Weckbecker. Unified greedy approximability beyond submodular maximization. SIAM Journal on Discrete Mathematics, 38(1):248–379, 2024. doi:10.1137/23M1569265.
[12] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, 1998. doi:10.1145/285055.285059.
[13] Michel X. Goemans and Jon M. Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111–124, 1998. doi:10.1007/BF01585867.
[14] Michel X. Goemans and Francisco Unda. Approximating incremental combinatorial optimization problems. In Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 6:1–6:14, 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.6.
[15] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. doi:10.1016/0304-3975(85)90224-5.
[16] Jeff Hartline and Alexa Sharp. An incremental model for combinatorial maximization problems. In Proceedings of the 5th International Workshop on Experimental Algorithms (WEA), pages 36–48, 2006. doi:10.1007/11764298.
[17] Jeff Hartline and Alexa Sharp. Incremental flow. Networks, 50(1):77–85, 2007. doi:10.1002/net.20168.
[18] Thomas Kalinowski, Dmytro Matsypura, and Martin W.P. Savelsbergh. Incremental network design with maximum flows. European Journal of Operational Research, 242(1):51–62, 2015. doi:10.1016/j.ejor.2014.10.003.
[19] Yasushi Kawase, Hanna Sumita, and Takuro Fukunaga. Submodular maximization with uncertain knapsack capacity. SIAM Journal on Discrete Mathematics, 33(3):1121–1145, 2019. doi:10.1137/18M1174428.
[20] Max Klimm and Martin Knaack. Maximizing a submodular function with bounded curvature under an unknown knapsack constraint. In Proceedings of the 25th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 49:1–49:19, 2022. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.49.
[21] Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. A general approach for incremental approximation and hierarchical clustering. SIAM Journal on Computing, 39(8):3633–3669, 2010. doi:10.1137/070698257.
[22] Nicole Megow and Julián Mestre. Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), pages 495–504, 2013. doi:10.1145/2422436.2422490.
[23] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816–832, 2003. doi:10.1137/S0097539701383443.
[24] Alfredo Navarra and Cristina M. Pinotti. Online knapsack of unknown capacity: How to optimize energy consumption in smartphones. Theoretical Computer Science, 697:98–109, 2017. doi:10.1016/j.tcs.2017.07.029.
[25] George Nemhauser, Laurence Wolsey, and Michael Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14:265–294, 1978. doi:10.1007/BF01588971.
[26] C. Greg Plaxton. Approximation algorithms for hierarchical location problems. Journal of Computer and System Sciences, 72(3):425–443, 2006. doi:10.1016/j.jcss.2005.09.004.
[27] Richard Rado. A theorem on independence relations. The Quarterly Journal of Mathematics, 13:83–89, 1942. doi:10.1093/qmath/os-13.1.83.
[28] Clemens Thielen, Morten Tiedemann, and Stephan Westphal. The online knapsack problem with incremental capacity. Mathematical Methods of Operations Research, 83(2):207–242, 2016. doi:10.1007/s00186-015-0526-9.
[29] Francisco T. Unda Surawski. Combinatorial Incremental Problems. PhD thesis, Massachusetts Institute of Technology, 2018. URL: https://dspace.mit.edu/bitstream/handle/1721.1/122890/1126788574-MIT.pdf?sequence=1&isAllowed=y.
[30] Xianbin Zhu, Wenjun Li, Yongjie Yang, and Jianxin Wang. Incremental algorithms for the maximum internal spanning tree problem. Science China Information Sciences, 64, May 2021. doi:10.1007/s11432-019-2630-2.

[bib.bib1] [1] Aaron Bernstein, Yann Disser, Martin Groß, and Sandra Himburg. General bounds for incremental maximization. Mathematical Programming, 191(2):953–979, 2022. doi:10.1007/s10107-020-01576-0.

[bib.bib2] [2] Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th Interantional Conference on Machine Learning (ICML), pages 498–507, 2017. URL: https://proceedings.mlr.press/v70/bian17a.html.

[bib.bib3] [3] Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. The minimum latency problem. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 163–171, 1994. doi:10.1145/195058.195125.

[bib.bib4] [4] Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. Paths, trees, and minimum latency tours. In 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 36–45, 2003. doi:10.1109/SFCS.2003.1238179.

[bib.bib5] [5] Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young. Incremental medians via online bidding. Algorithmica, 50(4):455–478, 2008. doi:10.1007/s00453-007-9005-x.

[bib.bib6] [6] Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19:1–34, 2018. URL: https://jmlr.org/papers/v19/16-534.html.

[bib.bib7] [7] Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial approximation for the incremental prize-collecting steiner-tree problem. In ESA 2024, pages 47:1–47:16, 2024. doi:10.4230/LIPIcs.ESA.2024.47.

[bib.bib8] [8] Yann Disser, Max Klimm, Annette Lutz, and David Weckbecker. Fractionally subadditive maximization under an incremental knapsack constraint. SIAM Journal on Discrete Mathematics, 38(1):764–789, 2024.

[bib.bib9] [9] Yann Disser, Max Klimm, Nicole Megow, and Sebastian Stiller. Packing a knapsack of unknown capacity. SIAM Journal on Discrete Mathematics, 31(3):1477–1497, 2017. doi:10.1137/16M1070049.

[bib.bib10] [10] Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker. Incremental maximization via continuization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261, pages 47:1–47:17, 2023. doi:10.4230/LIPIcs.ICALP.2023.47.

[bib.bib11] [11] Yann Disser and David Weckbecker. Unified greedy approximability beyond submodular maximization. SIAM Journal on Discrete Mathematics, 38(1):248–379, 2024. doi:10.1137/23M1569265.

[bib.bib12] [12] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, 1998. doi:10.1145/285055.285059.

[bib.bib13] [13] Michel X. Goemans and Jon M. Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111–124, 1998. doi:10.1007/BF01585867.

[bib.bib14] [14] Michel X. Goemans and Francisco Unda. Approximating incremental combinatorial optimization problems. In Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 6:1–6:14, 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.6.

[bib.bib15] [15] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. doi:10.1016/0304-3975(85)90224-5.

[bib.bib16] [16] Jeff Hartline and Alexa Sharp. An incremental model for combinatorial maximization problems. In Proceedings of the 5th International Workshop on Experimental Algorithms (WEA), pages 36–48, 2006. doi:10.1007/11764298.

[bib.bib17] [17] Jeff Hartline and Alexa Sharp. Incremental flow. Networks, 50(1):77–85, 2007. doi:10.1002/net.20168.

[bib.bib18] [18] Thomas Kalinowski, Dmytro Matsypura, and Martin W.P. Savelsbergh. Incremental network design with maximum flows. European Journal of Operational Research, 242(1):51–62, 2015. doi:10.1016/j.ejor.2014.10.003.

[bib.bib19] [19] Yasushi Kawase, Hanna Sumita, and Takuro Fukunaga. Submodular maximization with uncertain knapsack capacity. SIAM Journal on Discrete Mathematics, 33(3):1121–1145, 2019. doi:10.1137/18M1174428.

[bib.bib20] [20] Max Klimm and Martin Knaack. Maximizing a submodular function with bounded curvature under an unknown knapsack constraint. In Proceedings of the 25th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 49:1–49:19, 2022. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.49.

[bib.bib21] [21] Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. A general approach for incremental approximation and hierarchical clustering. SIAM Journal on Computing, 39(8):3633–3669, 2010. doi:10.1137/070698257.

[bib.bib22] [22] Nicole Megow and Julián Mestre. Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), pages 495–504, 2013. doi:10.1145/2422436.2422490.

[bib.bib23] [23] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816–832, 2003. doi:10.1137/S0097539701383443.

[bib.bib24] [24] Alfredo Navarra and Cristina M. Pinotti. Online knapsack of unknown capacity: How to optimize energy consumption in smartphones. Theoretical Computer Science, 697:98–109, 2017. doi:10.1016/j.tcs.2017.07.029.

[bib.bib25] [25] George Nemhauser, Laurence Wolsey, and Michael Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14:265–294, 1978. doi:10.1007/BF01588971.

[bib.bib26] [26] C. Greg Plaxton. Approximation algorithms for hierarchical location problems. Journal of Computer and System Sciences, 72(3):425–443, 2006. doi:10.1016/j.jcss.2005.09.004.

[bib.bib27] [27] Richard Rado. A theorem on independence relations. The Quarterly Journal of Mathematics, 13:83–89, 1942. doi:10.1093/qmath/os-13.1.83.

[bib.bib28] [28] Clemens Thielen, Morten Tiedemann, and Stephan Westphal. The online knapsack problem with incremental capacity. Mathematical Methods of Operations Research, 83(2):207–242, 2016. doi:10.1007/s00186-015-0526-9.

[bib.bib29] [29] Francisco T. Unda Surawski. Combinatorial Incremental Problems. PhD thesis, Massachusetts Institute of Technology, 2018. URL: https://dspace.mit.edu/bitstream/handle/1721.1/122890/1126788574-MIT.pdf?sequence=1&isAllowed=y.

[bib.bib30] [30] Xianbin Zhu, Wenjun Li, Yongjie Yang, and Jianxin Wang. Incremental algorithms for the maximum internal spanning tree problem. Science China Information Sciences, 64, May 2021. doi:10.1007/s11432-019-2630-2.

	$\displaystyle f(A\cup B)$	$\displaystyle=\|(A\cup B)\cap U_{i^{}}\|\cdot d_{i^{}}$
		$\displaystyle=\|A\cap U_{i^{}}\|\cdot d_{i^{}}+\|(B\setminus A)\cap U_{i^{}}\|% \cdot d_{i^{}}$
		$\displaystyle\leq\|A\cap U_{i^{}}\|\cdot d_{i^{}}+\|B\cap U_{i^{}}\|\cdot d_{i^% {}}$
		$\displaystyle\leq\bigl(\max_{i\in\mathbb{N}}\|A\cap U_{i}\|\cdot d_{i}\bigr)+% \bigl(\max_{i\in\mathbb{N}}\|B\cap U_{i}\|\cdot d_{i}\bigr)$
		$\displaystyle=f(A)+f(B).\$

Incremental Maximization for a Broad Class of Objectives

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our results

Definition 1.

Theorem 2.

Theorem 3.

Theorem 4.

Related work

2 Competitive Bounds

Observation 5.

Proof.

Theorem 6.

Proof.

Case 1: 𝑪<⌈𝜹⁢𝒄𝒊−𝟏⌉.

Case 2: ⌈𝜹⁢𝒄𝒊−𝟏⌉≤𝑪<𝒙.

Case 3: 𝑪≥⌈𝜹⁢𝒄𝒊−𝟏⌉, 𝑪≥𝒙.

Theorem 7.

Proof.

3 Incremental Maximization for Subclasses

3.1 Subadditivity

Proposition 8.

Proof.

Theorem 3. [Restated, see original statement.]

Definition 9.

Proposition 10.

Proof.

Corollary 11.

3.2 𝜸-𝜶-Augmentability

Proposition 12.

Proof.

Theorem 13.

References

Incremental Maximization
for a Broad Class of Objectives

Case 1: $C<\lceil\delta c_{i-1}\rceil$ .

Case 2: $\lceil\delta c_{i-1}\rceil\leq C<x$ .

Case 3: $C\geq\lceil\delta c_{i-1}\rceil$ , $C\geq x$ .

3.2 $\gamma$ - $\alpha$ -Augmentability