New Results on a General Class of Minimum Norm Optimization Problems

In many optimization problems, a feasible solution typically induces a multi-dimensional value vector (e.g., by the subset of elements of the solution), and the objective of the optimization problem is to minimize either the total sum (i.e., ${\mathrm{\ell }}_1$ norm) or the maximum (i.e., ${\mathrm{\ell }}_{\mathrm{\infty }}$ norm) of the vector entry. For example, in the minimum perfect matching problem, the solution is a subset of edges and the induced value vector is the weight vector of the matching (i.e., each entry of the vector is the weight of edge if the edge is in the matching and 0 for a non-matching edge) and we would like to minimize the total sum. Many of such problems are fundamental in combinatorial optimization but require different algorithms for their min-sum and min-max variants (and other possible variants). Recently there have been a rise of interests in developing algorithms for more general objectives, such as ${\mathrm{\ell }}_p$ norms [4, 24], top-$\mathrm{\ell }$ norms [22], ordered norms [9, 12] and more general norms [13, 14, 31, 19, 1, 33], as interpolation or generalization of min-sum and min-max objectives. The algorithmic study of such generalizations helps unify, interpolate and generalize classic objectives and algorithmic techniques.

The study of approximation algorithm for general norm minimization problems is initiated by Chakrabarty and Swamy [13]. They studied two fundamental problems, load balancing and $k$-clustering, and provided constant factor approximation algorithm for these problems. For load balancing, the induced value vector is the vector of machine loads and for $k$-clustering the vector is the vector of service costs. Subsequently, the norm minimization has been studied for a variety of other combinatorial problem such as general machine scheduling problem [19], stochastic optimization problems [31], online algorithms [38], parameterized algorithms [1] etc. In this paper, we study the norm optimization problem for a general set of combinatorial problems. In our problem, a feasible set is a subset of elements and the multi-dimensional value vector is induced by the subset of elements of the solution. Our problem is defined formally as follows:

Note that the case $f(𝒗[S])={\sum }_{e\in S}{v}_e$ is the most studied min-sum objective and we call the corresponding problem the original optimization problem. Other interesting norms include ${\mathrm{\ell }}_p$ norms, Top-$\mathrm{\ell }$ norms (the sum of top-$\mathrm{\ell }$ entries), ordered norms (see its definition in Section 3). Note that our general framework covers the $k$-clustering studied in [13]: in the $k$-clustering problem, the universe $𝒰$ is the set of edges and each feasible solution in $ℱ$ is a subset of edges that corresponds to a $k$-clustering. The load balancing problem does not directly fit into our framework, since one needs to first aggregate the processing times to machine loads, then apply the norm.

Before stating our results, we briefly mention some results that are either known or very simple to derive.

1. 1.

   (Matroid) Suppose the feasible set $ℱ$ is a matroid and a feasible solution is a basis of this matroid. In fact, the greedy solution (i.e., the optimal min-sum solution) is the optimal solution for any monotone symmetric norm. This is a folklore result and can be easily seen as follows: First, it is easy to establish the following observation, using the exchange property of matroid: We use ${\text{Top}}_{\mathrm{\ell }}(S)$ to denote the sum of largest $\mathrm{\ell }$ elements of $S$. For any $\mathrm{\ell }\in {\mathbb{Z}}_{\ge 1}$ and any basis $S\in ℱ$, ${\text{Top}}_{\mathrm{\ell }}(S_{\text{greedy}})\le {\text{Top}}_{\mathrm{\ell }}(S)$ where $S_{\text{greedy}}$ is the basis obtained by the greedy algorithm. Then using the majorization lemma by Hardy, Littlewood and Pòlya (Lemma 3), we can conclude $S_{\text{greedy}}$ is optimal for any monotone symmetric norm.

2. 2.

   (Vertex Cover) We first relax the problem to the following convex program:

   $$\text{min.}f(v_1{x}_1,\mathrm{\dots },v_n{x}_n)\text{s.t. }{x}_i+x_j\ge 1\text{ for any }(i,j)\in E.$$

   The objective is convex since $f$ is norm (in particular the triangle inequality of norm). Then, we solve the convex program and round all $x_i\ge 1/2$ to $1$ and others to $0$. It is easy to see this gives a 2-approximation (using the property $f(\alpha x)=\alpha f(x)$ for $\alpha \ge 0$).

3. 3.

   (Set Cover) The norm-minimization set cover problem is a special case of the generalized load balancing problem introduced in [19]. Here is the reduction: each element corresponds to a job and each subset to a machine; if element $i$ is in set $S_j$, the processing time $p_{ij}=1$, otherwise $p_{ij}=\mathrm{\infty }$; the inner norm of each machine is the max norm (i.e., ${\mathrm{\ell }}_{\mathrm{\infty }}$) and the outer norm is $f(\cdot )$. Hence, this implies an $O(\log n)$-approximation for norm-minimization set cover problem using the general result in [19]. The algorithm in [19] is based on a fairly involved configuration LP. In the full version [17], we also provide a much simpler randomized rounding algorithm that is also an $O(\log n)$-approximation. Note this is optimal up to a constant factor given the approximation hardness of set cover [23, 21].

4. 4.

   (${\text{Top}}_{\mathrm{\ell }}$ and Ordered Norms) If the min-sum problem can be solved or approximated efficiently, one can also solve or approximate the corresponding ${\text{Top}}_{\mathrm{\ell }}$ and ordered norm optimization problems. This mostly follows from known techniques in [9, 13, 22].

Throughout this paper, for vector $𝒗\in {ℝ}_{+}^n$, define ${𝒗}^{\downarrow }$ as the non-increasingly sorted version of $𝒗$, and $𝒗[S]={\{{𝒗}_j\cdot \mathrm{𝟏}[j\in S]\}}_{j\in [n]}$ for any $S\subseteq [n]$. Let ${\text{Top}}_k:{ℝ}^n\to {ℝ}_{+}$ be the top-$k$ norm that returns the sum of the $k$ largest absolute values of entries in any vector, $k\le |n|$. Denote $[n]$ as the set of positive integers no larger than $n\in \mathbb{Z}$, and $a^{+}=\max \{a,0\},a\in ℝ$.

We say function $f:{ℝ}^n\to {ℝ}_{+}$ is a norm if: (i) $f(𝒗)=0$ if and only if $𝒗=0$, (ii) $f(𝒖+𝒗)\le f(𝒖)+f(𝒗)$ for all $𝒖,𝒗\in {ℝ}^n$, (iii) $f(\theta 𝒗)=|\theta |f(𝒗)$ for all $𝒗\in {ℝ}^n,\theta \in ℝ$. A norm $f$ is monotone if $f(𝒗)\le f(𝒖)$ for all $0\le 𝒗\le 𝒖$, and symmetric if $f(𝒗)=f({𝒗}^{\prime })$ for any permutation ${𝒗}^{\prime }$ of $𝒗$. We are also interested in the following special monotone symmetric norms.

In this section, we provide an equivalent formulation for the general symmetric norm minimization problem MinNorm (up to constant approximation factor). Recall that as defined in Section 1, we are given a set $𝒰$ of $n$ elements, and $ℱ$ represents a family of feasible subsets of $𝒰$. The goal of MinNorm is to find a feasible subset $S\in ℱ$ to minimize $f(𝒗[S])$, where $f$ is a symmetric monotone norm function. We say that we find a $c$-approximation for the problem for some $c\ge 1$, if we can find an $S$ such that $f(𝒗[S])\le c\cdot f(𝒗[S^{\ast }])$, where $S^{\ast }$ is the optimal solution. Since a general norm function is quite abstract and hard to deal with, we formulate the following (equivalent, up to constant approximation factor) optimization problem which is more combinatorial in nature.

Notice that the structure of a problem is defined by $𝒰$ and $ℱ$ (for example, the vertex cover problem is given by vertex set $𝒰$ and $ℱ$ contains all subsets of $𝒰$ corresponding to a vertex cover), each problem corresponds to a MinNorm version and an LogBgt version. We show that solving LogBgt is equivalent to approximating MinNorm, up to constant approximation factors. In fact, the reduction from norm approximation to optimization problem with multiple budgets has been implicitly developed in prior work [13, 32]. For generality and ease of usage, we encapsulate the reduction in the following general theorem.

We defer the full details to the full version [17] and now outline the main ideas behind the proof.

In this section, we consider the multi-dimensional knapsack cover problem defined as follows.

In light of Theorem 5, we introduce $T=\lceil \log n\rceil$ disjoint sets $S_1,S_2,\mathrm{\dots },S_T$ and consider the LogBgt problem with $(𝒰;S_1,\mathrm{\dots },S_T;ℱ)$, which We denote as LogBgt-KnapCov. We consider LogBgt-KnapCov for two cases: (1) $d=O(1)$ and (2) $d=O(\sqrt{\log n/\log \log W})$ ($W$ will be defined in Section 5.2). For both cases, we use the following natural linear programming formulation for LogBgt-KnapCov :

For both cases, we develop a method called partial enumeration. Partial enumeration lists a subset of possible partial solutions for the first several groups. Here is the complete definition:

In this section, we study the norm minimization for the interval cover problem, which is defined as follows:

In light of Theorem 5, we can focus on obtaining a constant-factor approximation algorithm for $(c,c_0)$-LogBgt-IntCov. The input of a LogBgt-IntCov problem is a tuple ${\eta }^{\mathrm{int}}=({𝒰}^{\mathrm{int}};S_1^{\mathrm{int}},\mathrm{\dots },S_T^{\mathrm{int}};\mathrm{\Gamma })$, which is the LogBgt problem with input $({𝒰}^{\mathrm{int}};S_1^{\mathrm{int}},\mathrm{\dots },S_T^{\mathrm{int}};{ℱ}^{\mathrm{int}})$ where the set of feasible solutions is ${ℱ}^{\mathrm{int}}=\{D\subseteq {𝒰}^{\mathrm{int}}:\mathrm{\Gamma }\subseteq {\bigcup }_{I\in D}I\}$.

In this section, we begin by transforming the interval cover problem into a new problem called the tree cover problem. The definitions of both problems are provided in Section 6.1. These transformation results in only a constant-factor loss in the approximation factor (i.e., if a polynomial-time algorithm can solve $c$-LogBgt-TreeCov for some constant $c$, then there exists a polynomial-time constant-factor approximation algorithm for LogBgt-IntCov).

Next, we focus on LogBgt-TreeCov. We first employ the partial enumeration algorithm, as defined in Section 5, to list partial solutions for the first $T_0=\lfloor \log \log \log n\rfloor$ sets. The details of this process are provided in Section 6.2. Following partial enumeration, we apply a rounding algorithm to evaluate each partial solution. The entire rounding process is detailed in Section 6.3.

In this section, we argue that it may be challenging to achieve constant approximations for the norm optimization problems for perfect matching, $s$-$t$ path, and $s$-$t$ cut just by LP rounding. We show that the natural linear programs have large integrality gaps.

In light of Theorem 5, we can define the LogBgt-Path problem with input tuple ${\eta }^{\mathrm{path}}=({𝒰}^{\mathrm{path}};S_1^{\mathrm{path}},\mathrm{\dots },S_T^{\mathrm{path}};G^{\mathrm{path}};s;t)$, which is the LogBgt problem defined in Definition 4 with input $({𝒰}^{\mathrm{path}};S_1^{\mathrm{path}},\mathrm{\dots },S_T^{\mathrm{path}};{ℱ}^{\mathrm{path}})$.

We define the LogBgt-PerMat problem with ${\eta }^{\mathrm{pm}}=({𝒰}^{\mathrm{pm}};S_1^{\mathrm{pm}},\mathrm{\dots },S_T^{\mathrm{pm}};G^{\mathrm{cut}};s;t)$ as the LogBgt problem with $({𝒰}^{\mathrm{pm}};S_1^{\mathrm{pm}},\mathrm{\dots },S_T^{\mathrm{pm}};{ℱ}^{\mathrm{pm}})$.

Due to Theorem 5, we establish the equivalence between approximating the MinNorm problem and the LogBgt problem. Hence, if we can show that the LogBgt version is hard to approximate, then the same hardness (up to constant factor) also applies to the MinNorm version.

Now, we consider using the linear programming rounding approach to approximate the LogBgt problem with $\eta =(𝒰;S_1,\mathrm{\dots },S_T;ℱ)$. Such an algorithm proceeds according to the following pipeline:

• $\mathrm{■}$

  First, we formulate the natural linear program (for $c\ge 1$) as the following:

  	$\min$		$0$				(LP-LBO-Original($\eta$, $c$))
  	$s.t.$		$x$ satisfies		$\text{relaxed constraints of }ℱ,$
  	${\displaystyle \sum _{u\in S_i}}{x}_u\le c\cdot 2^i$		$\forall 1\le i\le T,$
  	$x_u\ge 0$		$\forall u\in 𝒰.$

• $\mathrm{■}$

  Then, to solve the $(c,c_0)$-LogBgt problem, we first check whether LP-LBO-Original($\eta$, $c_0$) has feasible solutions. If feasible, we use a rounding algorithm to find an integral solution for (LP-LBO-Original($\eta$, $c$)).

Since the factor $c$ in LP-LBO-Original($\eta$, $c$) determines the approximation factor, we study the following linear program.

Clearly, if LP-LBO-Original($\eta$, $c$) has a feasible solution, the optimal value of LP-LBO($\eta$) is at most $c$. Suppose we can round a fractional solution LP-LBO-Original($\eta$, $c$) to an integral feasible $c^{\prime }$-valid solution $\overline{x}$ for some constant $c^{\prime }$ (i.e., $\overline{x}$ satisfies $ℱ$ and ${\sum }_{u\in S_i}{\overline{x}}_u\le c^{\prime }\cdot 2^i\forall 1\le i\le T$). Then, we get an integral solution for LP-LBO($\eta$) with objective value $c^{\prime }$, contradicting the fact that the integrality gap of LP-LBO($\eta$) is $\omega (1)$. Hence, we can conclude that if the integrality gap of LP-LBO($\eta$) is $\omega (1)$, it would be difficult to derive a constant factor approximation algorithm for both LogBgt and MinNorm-version of the problem using the LP LP-LBO-Original($\eta ,c$).

Recall that we define the MinNorm-Path problem and prove that the natural linear program has a large integrality gap in Section 7. In this section, we provide a factor $\alpha$ approximation algorithm that runs in $n^{O(\log \log n/\alpha )}$ time, for any $9\le \alpha \le \log \log n$. In particular, this implies an $O(\log \log n)$-factor polynomial-time approximation algorithm and a constant-factor quasi-polynomial $n^{O(\log \log n)}$-time algorithm for MinNorm-Path. Note that this does not contradict Theorem 21, since we do not use the LP rounding approach in this section.

In light of Theorem 5 with $\epsilon =1$, we consider $\frac{\alpha -1}{4}$-LogBgt-Path problem, with input tuple $\eta =(𝒰;S_1,S_2,\mathrm{\dots },S_T;G;s;t)$, where $n=|𝒰|$ and $T=\lceil \log n\rceil$, where $\alpha$ is the approximation factor we aim to achieve.

We first provide an overview of our main ideas. A natural approach to solve LogBgt-Path is to employ dynamic programming, in which the states keep track of the number of edges used from each group. However, since we have $T=\lceil \log n\rceil$ groups, the number of states may be as large as $n^{O(T)}$. To resolve this issue, we perform an approximation dynamic programming, in which we only approximate the number of edges in each group. In particular, the numbers are rounded to the nearest power of $p$ after each step, for carefully chosen value $p>1$ (to ensure that we do not lose too much in the rounding). This rounding technique is inspired by a classic approximation algorithm for the subset sum problem [30] Now, the dynamic programming state is a vector that approximates the number of edges used from each group in a path from $x$ to $y$ with at most $2^i$ edges, where $x,y\in V$ and $0\le i\le \lceil \log n\rceil$. The dynamic programming process involves storing the number of selected items in each group and rounding them to the nearest power of $p$ at each iteration. However, this method results in a state space of size ${({\log }_{p}n)}^T=n^{\mathrm{\Omega }(\log \log n)}$, which is better than $n^{O(T)}$, but still super-polynomial. To resolve the above issue, we need the second idea, which is to trade off the approximation factor and the running time. In particular, we introduce an integer parameter $\beta$, defined as $\beta =\frac{\alpha -1}{4(1+\delta )}$ for some $\delta \in [\frac{1}{2},2]$. We then partition the original $T$ groups into $T/\beta$ supergroups, each containing $\beta$ groups. This reduces the number of states to ${({\log }_{p}n)}^{O(T/\beta )}$, but incurs a loss of $O(\beta )$ in the approximation factor.

Now, we present the details of our algorithm. Let $K=\lceil T/\beta \rceil$, and $B_i=\min (T,i\cdot \beta )$ for all $0\le i\le K$. For $1\le i\le K$ and $D\subseteq 𝒰$, define $C_i(D)={\sum }_{j=B_{i-1}+1}^{B_i}\frac{1}{2^j}|D\cap S_j|$ (specifically, $C_i(\mathrm{\varnothing })=0$). Furthermore, we define the vector $C(D)=(C_1(D),\mathrm{\dots }{C}_K(D))\in {ℝ}^K$. It is important to notice that: