LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization

We consider the class of disjoint bilinear programs $$ \max \, \{ {\textbf{x}}^T{\textbf{y}} \mid {\textbf{x}} \in {\mathcal {X}}, \;{\textbf{y}} \in {\mathcal {Y}}\}$$ where $${\mathcal {X}}$$ and $${\mathcal {Y}}$$ are packing polytopes. We present an $$O(\frac{\log \log m_1}{\log m_1} \frac{\log \log m_2}{\log m_2})$$ -approximation algorithm for this problem where $$m_1$$ and $$m_2$$ are the number of packing constraints in $${\mathcal {X}}$$ and $${\mathcal {Y}}$$ respectively. In particular, we show that there exists a near-optimal solution $$(\tilde{{\textbf{x}}}, \tilde{{\textbf{y}}})$$ such that $$\tilde{{\textbf{x}}}$$ and $$\tilde{{\textbf{y}}}$$ are "near-integral". We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique. As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an $$O(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L})$$ -approximation where L is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an $$O(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L})$$ -approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance.