Idioma:

A note on degree vs gap of Min-Rep Label Cover and improved inapproximability for connectivity problems

Manurangsi, Pasin

Information processing letters, 2019-05, Vol.145, p.24-29 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
A note on degree vs gap of Min-Rep Label Cover and improved inapproximability for connectivity problems
Autor: Manurangsi, Pasin
Assuntos: Computational Complexity ; Connectivity Problems ; Hardness of Approximation ; Label Cover
É parte de: Information processing letters, 2019-05, Vol.145, p.24-29
Descrição: •An improved analysis for sparsification of Label Cover with better degree dependency.•Implies improved inapproximability for connectivity problems. This note concerns the trade-off between the degree of the constraint graph and the gap in hardness of approximating the Min-Rep variant of Label Cover (aka Projection Game). We make a very simple observation that, for NP-hardness with gap g, the degree can be made as small as O(glog⁡g), which improves upon the previous O˜(g2) bound from the work of Laekhanukit [15]. Note that our bound is optimal up to a logarithmic factor since there is a trivial Δ-approximation for Min-Rep where Δ is the maximum degree of the constraint graph. Thanks to known reductions [10,8,11,15], this improvement implies better hardness of approximation results for Rooted k-Connectivity, Vertex-Connectivity Survivable Network Design and Vertex-Connectivity k-Route Cut.
Editor: Elsevier B.V
Idioma: Inglês

Voltar para lista de resultados