ECCC-Report TR16-017https://eccc.weizmann.ac.il/report/2016/017Comments and Revisions published for TR16-017en-usFri, 05 Feb 2016 12:51:28 +0200
Paper TR16-017
| Limitations of Linear Programming Techniques for Bounded Color Matchings |
Georgios Stamoulis
https://eccc.weizmann.ac.il/report/2016/017Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions $\alpha_1, \dots, \alpha_{\ell}$ assigning positive numbers to each edge and $\ell$ numbers $\beta_1, \dots, \beta_{\ell} \in \mathbb{Q^+}$, each one associated with the corresponding length function. The goal is to find a maximum weight matching $M$ (under function $w$) such that $\sum_{e \in M} \alpha_i (e) \leq \beta_i$, $\forall i \in [\ell]$ (these are the budgets). In this paper we are interested in the case where each edge $e \in E$ belongs to a unique budget, i.e., it has a unique \textit{color}. In \cite{DBLP:conf/mfcs/Stamoulis14} an $\frac{1}{2}$-approximation algorithm was given based on rounding the natural linear programming relaxation of the problem, and this is optimal modulo the integrality gap of the formulation. The purpose of this paper is to study to what extend linear programming methods help us design algorithms with a better performance guarantee. We prove the following \textit{unconditional} inapproximability result: even a large family of linear programs, generated by a \textit{logarithmic} number of rounds of the Sherali-Adams hierarchy \cite{DBLP:journals/siamdm/SheraliA90} or a \textit{linear} number of rounds of the \textsf{BCC} operator \cite{DBLP:journals/mp/BalasCC93}, does not suffice to change the integrality gap even the slightest.Fri, 05 Feb 2016 12:51:28 +0200https://eccc.weizmann.ac.il/report/2016/017