[This is a supplementary material to Section 4.2.4 of Chapter 4]
Approximating hypergraph matchings by (max,+) circuits is hard
As shown in Section 4.2.4 of the book,
the maximization problem on any polynomial $(m,d)$-design $\f\subseteq 2^{[n]}$
requires large $(\max,+)$ circuits to approximate it within a factor $r$
twice smaller than $m/d$ (Corollary 4.24), but can be easily approximated within the factor $r=m/d$ (Proposition 4.23).
This does not show that the greedy algorithm can outperform approximating $(\max,+)$ circuits, because the greedy algorithm cannot achieve any smaller than $r=m/d$ approximation factor for this problem.
To show this, take $\epsilon>0$ arbitrarily small, and set
$c:=1/(1-\epsilon/2)>1$. Take arbitrary two sets $A\neq B\in\f$,
and a subset $S\subset A$ of $|S|=d$ elements. Since $\f$ is an
$(m,d)$-design, $S$ cannot be contained in $B$. So, give weight
$c>1$ to all elements of $S$, weight $1$ to all elements of
$B\setminus S$, and zero weight to the rest. Then the maximizing
(best-in) greedy algorithm picks elements of weight $c$ first,
gets all $|S|=d$ of them, but then is stuck because no element of
weight $1$ fits; hence, the greedy algorithm achieves the total
weight $c|S|=c d$. But the optimum is at least
$|B|=m$. Hence, the approximation factor is at least $m/c
d=(1-\epsilon/2)m/d >(1-\epsilon)m/d$.
$\Box$
More on greedy algorithms can be found in this comment.
To show that the greedy algorithm can still outperform
approximating $(\max,+)$ circuits, another maximization
problem was considered in [1]: maximum weight perfect matchings in
a complete $k$-partite
hypergraph $K_{m,\ldots,m}$ with $m$ vertices in each part.
(In the literature, such a graph is also called complete $k$-partite $k$-uniform hypergraph: "$k$-uniform" because each (hyper-) edge has exactly $k$ vertices, and "$k$-partite" because we have $k$ parts.)
In $K_{m,\ldots,m}$, we have a set $V=V_1\cup \cdots\cup V_k$ of $|V|=mk$
vertices decomposed into $k$ disjoint blocks $V_1,\ldots,V_k$, each of
size $m$. Edges (called also hyperedges) are $k$-tuples $e\in
V_1\times \cdots\times V_k$. The ground set
\[
E=V_1\times \cdots\times V_k
\]
consists of all
$|E|=m^k$ edges. Two edges are disjoint if they differ in all
$k$ positions. A matching is a set of disjoint edges, and is a
perfect matching if it has the maximum possible number $m$ of
edges.
Fig 1:
A $k$-partite $k$-uniform hypergraph
for $k=4$ with $m=5$ vertices in each block (part), and a perfect matching in it.
The family $\f_{m,k}$ of feasible solutions of our problem consists of
all $|\f_{m,k}|=(m!)^{k-1}$ perfect matchings. So, the maximization
problem on $\f_{m,k}$ is, given an assignment of nonnegative weights
$x_e$ to the edges $e\in E$, to compute the maximum total weight
\[
f(x)=\max\left\{x_{e_1}+\cdots+x_{e_m}\colon e_i\in E\,, \mbox{ and
$e_i$ and $e_j$ are disjoint for all $i\neq j$ }\right\}
\]
of a perfect matching. Note that in the case $k=2$, $\f_{m,k}$
consists of perfect matchings in $K_{m,m}$, and the problem is to
compute the maximum weight of such a perfect matching.
The greedy algorithm can approximate the maximization problem on
$\f_{m,k}$ within the factor $k$ by just always picking the heaviest
of the remaining edges, untouched by the partial matching picked so
far. On the other hand, we have the following lower bound for
$(\max,+)$ circuits approximating this problem.
Theorem A: Let $m$ be a sufficiently large integer, and $k=k(m)$ be an integer
such that $6\leq k\leq \log \sqrt{m}$. If the allowed approximation factor is $r\leq 2^k/9$, then
\[
\Max{\f_{m,k}}{r}=2^{\Omega(\sqrt{m})}\,.
\]
Note that the lower bound holds even if the allowed approximation factor $r$ for $(\max,+)$ circuits is
exponential in the approximation factor $k$ achieved by the greedy algorithm.
Proof:
As done in Section 4.2.4 of the book in the case of maximization problems on designs, we will use the rectangle bound (Lemma 4.20(1)), but this time with the balance parameter
$\gamma:=2/3$ (not $\gamma=2$) to have $\gamma/2=1-\gamma$.
So, take an arbitrary
rectangle $\R=\A\lor \B$ lying below $\f=\f_{m,k}$ (this means that every set of $\R$ is contained in at least one set of $\f$). Hence, sets in
$\A$ and in $\B$ are subsets of (hyper-)edges $e\in V_1\times
\cdots\times V_k$. Since $\R$ lies below our family $\f$, and $\f$
consist of (perfect) matchings, all sets $A\cup B$ with $A\in\A$ and
$B\in\B$ must also be matchings.
Take the integer $d:=\lceil
m/3r\rceil$.
Each perfect matching $F\in \f=\f_{m,k}$ has size $|F|=m$ (consists of $m$ disjoint edges).
Note that for $\gamma=2/3$, we have that
both $\tfrac{\gamma}{2}$ and $1-\gamma$ are equal to $1/3$.
Hence, the inequalities right after Eq. (4.2) in this(1) footnote turn into:
\[
|F\cap A|\geq \frac{\gamma}{2r}\cdot |F|
= \frac{m}{3r}=d\ \ \mbox{ and }\ \
|F\cap B|\geq \frac{1-\gamma}{r}\cdot |F|=\frac{m}{3r}=d\,.
\]
By Lemma 4.20(1), it is enough to show
that $|\f|/|\f_{\R}|=2^{\Omega(\sqrt{m})}$ holds for the family
of perfect matchings:
\[
\f_{\R}=\{F\in\f\colon \mbox{$|F\cap A|\geq d$ and $|F\cap B|\geq d$
for some $A\in\A$ and $B\in\B$ }\}\,.
\]
Let
$S\subseteq V$ be the set of vertices belonging to at least one edge
of a matching in $\A$, and $T\subseteq V$ be the set of vertices
belonging to at least one edge of a matching in $\B$.
Since the rectangle $\R=\A\lor \B$ is cross-disjoint, we know that
the matchings $A\in\A$ and $B\in\B$ must be edge-disjoint, that is,
$A\cap B=\emptyset$ must hold. However, since the sets $A\cup B$
are matchings (the rectangle $\R$ lies below the family $\f$ of all perfect matchings), we actually know that
matchings $A$ and $B$ are even vertex-disjoint. Thus, we have a crucial property:
\[
S\cap T=\emptyset\,.
\]
Call a matching $A\subseteq V_1\times\cdots\times V_k$ an
$S$-matching if $A\subseteq (V_1\cap S)\times\cdots\times
(V_k\cap S)$ holds, that is, if edges of $A$ only match vertices of
$S$; $T$-matchings are defined similarly. By the definition
of $\f_{\R}$, every perfect matching $F\in\f_{\R}$ has at least $d$
edges lying in $(V_1\cap S)\times\cdots\times (V_k\cap S)$, and at
least $d$ edges lying in $(V_1\cap T)\times\cdots\times (V_k\cap
T)$. In particular, every perfect matching $F\in\f_{\R}$ must
contain at least one matching $A\cup B$, where $A$ is an
$S$-matching with $|A|=d$ edges and $B$ is a $T$-matching with
$|B|=d$ edges. It therefore suffices to upper-bound the number of
perfect matchings $F\in\f$ with this property.
We can pick any such pair $(A,B)$ of matchings as follows. Let $S_i=S\cap V_i$
and $T_i=T\cap V_i$ for $i=1,\ldots,k$. We can assume that each of
these $2k$ sets has at least $d$ vertices, for otherwise none of the
$S$-matchings or of the $T$-matchings could have $\geq d$ edges,
implying that $\f_{\R}=\emptyset$.
Pick in each $S_i$ a subset $S_i'\subseteq S_i$ of
$|S_i'|=d$ vertices, and in each $T_i$ a subset $T_i'\subseteq
T_i$ of $|T_i'|=d$ vertices. There are at most
\[
\prod_{i=1}^k\binom{m_i}{d}\binom{m-m_i}{d} \leq \binom{m}{2d}^k
\]
possibilities to do this, where $m_i=|S_i|$.
Pick a perfect matching $A$ in $S_1'\times \cdots
\times S_k'$ and a perfect matching $B$ in $T_1'\times \cdots
\times T_k'$. There are only
$\left[(d!)^{k-1}\right]^2=(d!)^{2(k-1)}$ possibilities to do
this.
After a pair $(A,B)$ of matchings is picked, there are at most
$[(m-2d)!]^{k-1}$ possibilities to extend the matching $A\cup B$ to a perfect
matching. Thus,
\[
|\f_{\R}| \leq \binom{m}{2d}^{k} (d!)^{2(k-1)} [(m-2d)!]^{k-1}
% = \binom{m}{2d}\left[m!\cdot \frac{(d!)^2}{(2d)!} \right]^{k-1}
= \binom{m}{2d}\left[m!\cdot \binom{2d}{d}^{-1} \right]^{k-1}\,,
\]
where the equality follows because $\binom{m}{2d}=m!/(2d)!(m-2d)!$
and $(2d)!/(d!)^2=\binom{2d}{d}$. Since there are $|\f|=(m!)^{k-1}$
perfect matchings, the rectangle bound (Lemma 4.20(1) ) yields the
following lower bound on $t=\Max{\f}{r}$:
\begin{equation}\label{eq:hyper}
t \geq \frac{|\f|}{|\f_{\R}|} \geq
\frac{\binom{2d}{d}^{k-1}}{\binom{m}{2d}} \geq
\left(\frac{2^{2d}}{d}\right)^{k-1}\cdot \left(\frac{2d}{\euler
m}\right)^{2d}=\frac{1}{d^{k-1}}\left(\frac{2^kd}{\euler
m}\right)^{2d} \geq \frac{1}{d^{k-1}}\left(\frac{2^k}{3\euler
r}\right)^{2d}\,,
\end{equation}
where the second inequality follows from the inequalities
$\binom{m}{2d}\leq (\euler m/2d)^{2d}$ and $\binom{2d}{d}\geq
2^{2d}/\sqrt{4d}\geq 2^{2d}/d$, and the last inequality follows
because (by our choice) $d=\lceil m/3r\rceil\geq m/3r$. Our
approximation factor is $r= 2^k/9$; hence, $d\geq m/3r=3m/2^k$ and $2^k/3\euler r=3/\euler$. Since clearly $d\leq m$,
the factor $1/d^{k-1}$ in Eq. \eqref{eq:hyper} is not greater than $m^{-k}$, and
we have
a lower bound
\[
t\geq \left(\frac{3}{\euler}\right)^{6m/2^k}\cdot d^{-k} \geq 2^{0.8
m/2^k - k\log m }\,.
\]
From our assumption $k\leq \log \sqrt{m}$, we have $m/2^k\geq
\sqrt{m}\gg k\log m$, and the desired lower bound $t\geq
2^{\Omega(m/2^k)}\geq 2^{\Omega(\sqrt{m})}$ follows.
∎
Remark: The reason why this argument fails for
bipartite graphs ($k=2$) and
the factor $r=2$ is numerical: in this case, we would only have
$2^k/3\euler r=2/3\euler \lt 1$ in Eq. \eqref{eq:hyper}, and the lower bound would be trivial. On the other hand, the argument used for larger values of $k$ is quite
"brutal," and it could apparently be possible to find non-trivial upper bounds on $|\f_{\R}|$ also in the case $k=2$ by going deeper in the special properties of perfect matchings in $K_{m,m}$.
$\Box$
Jump back ☝