Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-017 | 24th December 2015 18:40

Limitations of Linear Programming Techniques for Bounded Color Matchings


Authors: Georgios Stamoulis
Publication: 5th February 2016 12:51
Downloads: 2113


Given 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.

ISSN 1433-8092 | Imprint