Matroids, greedy algorithm and approximating tropical circuits

1. Matroids

• if $a\neq b\in A$, then for every position $i\in\supp{a}\setminus\supp{b}$ (that is, $a_i=1$ and $b_i=0$) there is a position $j\in\supp{b}\setminus\supp{a}$ (that is, $a_i=0$ and $b_i=1$) such that the vector $a-\vec{e}_i+\vec{e}_j$ belongs to $A$.

The vector $a-\vec{e}_i+\vec{e}_j$ is obtained from $a$ by switching the $i$th position from $1$ to $0$ and switching the $j$th position from $0$ to $1$: \[ \begin{array}{rcccccc} & & & i & & j & \\ a & = & \cdots & 1 & \cdots\cdots & 0 & \cdots \\ a-\vec{e}_i+\vec{e}_j & = & \cdots & 0 & \cdots\cdots & 1 & \cdots \end{array} \]

By a classical result of Rado [2], both the maximization and the minimization problems on matroids $A$ can be solved (exactly, within approximation factor $r=1$) by the greedy algorithm which we recall in the Appendix below.

The following simple proposition gives us a lot of matroids. Let $\slice{n}{m}\subseteq \{0,1\}^n$ be the set of all $|\slice{n}{m}|=\binom{n}{m}$ vectors $a\in \{0,1\}^n$ with $a_1+\cdots+a_n=m$ ones. A set $B\subseteq \{0,1\}^n$ is a Hamming set if every two distinct its vectors differ in more than two positions. Lemma 4.12 in the book shows that there are at least $2^{\binom{n}{m}/n}$ Hamming sets $B\subseteq \slice{n}{m}$. In Remark 4.14 of the book, the following fact was shown (in terms of families of sets instead of sets of their characteristic $0$-$1$ vectors).

Proposition: Let $3\leq m\leq n-2$. For every Hamming set $B\subseteq \slice{n}{m}$, the set $A=\slice{n}{m}\setminus B$ is a matroid.

So, take any two positions $j\neq l\in \supp{b}\setminus \supp{a}$, and consider the vectors $c=a-\vec{e}_i+\vec{e}_j$ and $d=a-\vec{e}_i+\vec{e}_l$. Since the basis exchange axiom fails for the set $A$, neither $c$ nor $d$ can belong to $A$; hence, both vectors $c$ and $d$ belong to the set $B\setminus\slice{n}{m}$. But these two vectors differ in only two positions ($j$ and $k$), a contradiction with $B$ being a Hamming set. ∎

That tropical circuits can considerably outperform the greedy algorithm is long known. For example, there are explicit sets $A\subseteq\{0,1\}^n$ of feasible solutions such that both maximization and minimization problems on $A$ can be exactly solved by $(\max,+)$ and $(\min,+)$ circuits of small size, but the greedy algorithm cannot even approximate any of these two problems within any factor $r\lt n-1$ (see Fact 2 in the Appendix).

Hence, a natural question arises: can also greedy substantially outperform tropical circuits? The following Fact 1 shows: yes, sometimes it can.

2. Known gaps

• between $f(x)$ and $r\cdot f(x)$, in the case when $f$ is a minimization problem;
• between $f(x)/r$ and $f(x)$, in the case when $f$ is a maximization problem.

Thus, $\Min{A}{r}\geq t$ means that for every $(\min,+)$ circuit $\Phi$ of size $\lt t$ there is an input weighting $x\in\RR_+^n$ such that either $\Phi(x) \lt f(x)$ (the circuit wrongly outputs better than optimal value) or $\Phi(x) \gt r\cdot f(x)$ (the value computed by the circuit is larger than $r$ times the optimal value).

We have the following fact (as a direct consequence of Corollary 4.13 and Remark 4.12 in the book).

Fact 1: There is a family $\A\subseteq 2^{n]}$ of $|\A|=2^{2^{\Omega(n)}}$ matroids $A\subseteq\{0,1\}^n$ such that the following holds for each $A\in\A$.

1. $\Min{A}{r}\geq \Bool{A}=2^{\Omega(n)}$ for any finite approximation factor $r\geq 1$;
2. $\Max{A}{r}=2^{\Omega(n)}$ for $r=1$;
3. $\Max{A}{r}=O(n^2)$ for $r=1+o(1)$.

Moreover, the maximization problem on all these matroids $A$ can be approximated with a factor $r=1+o(1)$ by one single $(\max,+)$ circuit of size $O(n^2)$.

Fact 1 raises several problems.

3. Matroids and $(\lor,\land)$ circuits

Problem 1: Exhibit an explicit matroid $A\subseteq\{0,1\}^n$ for which $\Bool{A}$ is super-polynomial.

4. Matroids and approximating (max,+) circuits

Problem 2: Are there matroids $A\subseteq\{0,1\}^n$ for which $\Max{A}{r}=\Omega(n^3)$ holds for some factor $r = 1+\epsilon$ with a constant $\epsilon >0$?

5. Spanning trees

On the other hand, we know (Theorem 3.16 in the book) that both $\Min{\spol{n}}{r}=2^{\Omega(\sqrt{n})}$ and $\Max{\spol{n}}{r}=2^{\Omega(\sqrt{n})}$ hold for the approximation factor $r=1$ (exactly solving tropical circuits).

Problem 3: Is $\Min{\spol{n}}{2}$ and/or $\Max{\spol{n}}{2}$ polynomial in $n$?

6. Perfect matchings

On the other hand, we know (Theorem 3.6 in the book) that $\Max{\PM_n}{r}=2^{\Omega(n)}$ holds for the approximation factor $r=1$ (exactly solving tropical circuits).

Problem 4: Is $\Max{\PM_n}{2}$ polynomial in $n$?

Appendix: greedy algorithms

• Maximization (best-in strategy): Start with the all-$0$ vector $b:=\vec{0}$ and iteratively do the following, where $b\in\{0,1\}^n$ is the vector obtained from $\vec{0}$ after $i-1$ steps.

  • At the $i$th step, set $b:=b+\vec{e}_i$ iff vector $b+\vec{e}_i$ is contained in at least one feasible solution, that is, iff $b+\vec{e}_i\leq a$ holds for at least one vector $a\in A$. In this case, we say that the position $i$ was accepted.

  • After all $n$ positions are treated, the algorithm outputs $\skal{b,x}=b_1x_1+\cdots+b_nx_n$.

• Minimization (worst-out strategy): Start with the all-$1$ vector $b:=\vec{1}$ and iteratively do the following, where $b\in\{0,1\}^n$ is the vector obtained from $\vec{1}$ after $i-1$ steps.

  • At the $i$th step, set $b:=b-\vec{e}_i$ iff vector $b-\vec{e}_i$ contains at least one feasible solution, that is, iff $b-\vec{e}_i\geq a$ holds for at least one vector $a\in A$. In this case, we say that the position $i$ was rejected.

  • After all $n$ positions are treated, the algorithm outputs $\skal{b,x}=b_1x_1+\cdots+b_nx_n$.

Remark 2: The choice of these special strategies (first-in for maximization and first-out for minimization) is not an accident. Namely, the greedy algorithm starting with the lightest-first ordering $x_1\leq x_2\leq \ldots\leq x_n$, and using the worst-out strategy for maximization or best-in strategy for minimization would be unable to approximate some optimization problems within any finite factor. To give a simple example, consider the path with three nodes

and let $A\subseteq \{0,1\}^3$ consist of the two characteristic $0$-$1$ vectors of the two maximal independent sets $\{a,c\}$ and $\{b\}$ of this path. If we take an arbitrarily large number $M>1$, and give weights $x_a=0$, $x_b=1$ and $x_c=M$, then both these greedy algorithms will treat the vertices in the order $a,b,c$. The worst-out maximizing greedy on $A$ would output $x_b=1$ while the optimum is $M$, and the best-in greedy for minimization would output $x_a+x_c=0+M$, while the optimum is $1$. In both cases, the achieved approximation factor is $r\geq M$ (arbitrarily large).    $\Box$

The following simple fact shows that on some sets $A\subseteq\{0,1\}^n$ of feasible solutions, the greedy algorithm can fail to achieve small approximation factors even when using "right" strategies (best-in for maximization and worst-out for minimization). Say that a set $A\subseteq\{0,1\}^n$ is $m$-bounded if no its vector has more than $m$ $1$s.

Fact 2: For any integer $1\leq m\lt n$, the greedy algorithm approximates the optimization (maximization and minimization) problem on every $m$-bounded set $A\subseteq\{0,1\}^n$ within the factor $r_A\leq m$, and there are (explicit) $m$-bounded antichains $A\subseteq\{0,1\}^n$ such that $r_A\geq m$ whereas $\Max{A}{r}\leq m$ and $\Min{A}{r}\leq m$ hold for the factor $r=1$.

Case 1: We deal with the maximizing (best-in) greedy algorithm. Let $i\in [n]$ be the first accepted element. Then $i$ is the first element belonging to at least one feasible set. So, $T\cap \{1,\ldots,i-1\}=\emptyset$, implying that $\skal{b,x}\leq |T|\cdot x_i\leq m\cdot x_i\leq m\cdot \skal{a,x}$, as desired.

Case 2: We deal with the minimizing (worst-out) greedy algorithm. Let $i\in [n]$ be the first not rejected element. Then the set $\{i+1,\ldots,n\}$ cannot contain any feasible solution (for otherwise, $i$ would not be rejected). But then $\skal{b,x}\geq x_{i-1}\geq x_i$, whereas $\skal{a,x}\leq |S|\cdot x_i\leq m\cdot x_i$, implying that $\skal{b,x}\leq m\cdot \skal{a,x}$, as desired.

To show that $r_A\geq m$ holds for some $m$-bounded antichain $A\subseteq\{0,1\}^n$, it is enough to show that $r_A > (1-\epsilon)m$ holds for arbitrarily small number $\epsilon \gt 0$. Consider the $m$-bounded antichain $A=\{\vec{e}_1, \vec{e}_2+\cdots+\vec{e}_{m+1}\}$ consisting of just two vectors. Give weight $x_1:=1/(1-\epsilon)\gt 1$ to the first element, weights $x_2=x_3=\ldots=x_n:=1$ to the next $m$ elements, and zero weight to the remaining $n-(m+1)$ ground elements $i\in[n]$. The maximizing (best-in) greedy will output $x_1$ while the optimum is $x_2+\cdots+x_{m+1}=m$, and the minimizing (worst-out) greedy algorithms will output $x_2+\cdots+x_{m+1}=m$ while the optimum is $x_1$. In both cases, the achieved approximation factor is $r\geq m/x_1 \gt (1-2\epsilon)m$.

The upper bounds $\Max{A}{1}\leq m$ and $\Min{A}{1}\leq m$ for this particular set $A$ are trivial because the maximization and minimization problems on $A$ are to compute the maximum or the minimum of $x_1$ and $x_2+\cdots+x_{m+1}$.      $\Box$

Remark 3: By Fact 2, the greedy algorithm (using "right" strategies, the best-in for maximization and worst-out for minimization) can approximate both optimization problems on any set $A\subseteq\{0,1\}^n$ within (a possibly large by bounded) factor $r\leq n$. The algorithm first sorts the input weights (this can be easily done), and then performs only $n$ steps. Note, however, that unlike the best-in strategy used for maximization. the worst-out strategy used for minimization can be rather difficult to implement efficiently. The point is that this strategy may be forced to solve (at each step) hard (even NP-hard) decision problems: does the remaining set of ground elements still contains at least one feasible solution? For example, in the case of the lightest $k$-clique problem for $k=n/2$, the oracle must be able to solve, in each step, an NP-complete problem: does the current graph still contains a $k$-clique?      $\Box$

References:

1. S. Jukna and H. Seiwert: Approximation limitations of pure dynamic programming, SIAM J. Comput., 49:1 (2020) 170-207.    arxiv
2. R. Rado: A theorem on independence relations, Quart. J. Math. 13 (1942) 83-89.