In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the problem. Our algorithm computes a (2+epsilon)-approximate solution which violates the capacity constraints by a factor of (4+epsilon) in a polylogarithmic number of communication rounds. On the other hand, we also show that every efficient distributed approximation algorithm for this problem must violate the capacity constraints. Our result is achieved in two steps. We first develop a 2-approximate, sequential primal-dual algorithm that violates the capacity constraints by a factor of 2. Subsequently, we present a distributed version of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchronization which forces any naive distributed implementation to use a linear number of communication rounds. The challenge in this step is therefore to achieve a reduction of the communication complexity to a polylogarithmic number of rounds without worsening the approximation guarantee.

Grandoni, F., Konemann, J., Panconesi, A., Sozio, M. (2008). A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM JOURNAL ON COMPUTING, 38(3), 825-840 [10.1137/06065310X].

A primal-dual bicriteria distributed algorithm for capacitated vertex cover

GRANDONI, FABRIZIO;
2008-01-01

Abstract

In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the problem. Our algorithm computes a (2+epsilon)-approximate solution which violates the capacity constraints by a factor of (4+epsilon) in a polylogarithmic number of communication rounds. On the other hand, we also show that every efficient distributed approximation algorithm for this problem must violate the capacity constraints. Our result is achieved in two steps. We first develop a 2-approximate, sequential primal-dual algorithm that violates the capacity constraints by a factor of 2. Subsequently, we present a distributed version of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchronization which forces any naive distributed implementation to use a linear number of communication rounds. The challenge in this step is therefore to achieve a reduction of the communication complexity to a polylogarithmic number of rounds without worsening the approximation guarantee.
2008
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Con Impact Factor ISI
Approximation algorithms; Distributed algorithms; Primal-dual algorithms; Vertex cover
Grandoni, F., Konemann, J., Panconesi, A., Sozio, M. (2008). A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM JOURNAL ON COMPUTING, 38(3), 825-840 [10.1137/06065310X].
Grandoni, F; Konemann, J; Panconesi, A; Sozio, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
GKPS08sicomp.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Licenza: Creative commons
Dimensione 252.29 kB
Formato Adobe PDF
252.29 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

Questo articolo è pubblicato sotto una Licenza Licenza Creative Commons Creative Commons

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/31148
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 20
social impact