Document Open Access Logo

An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity

Authors Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao, Kunihiko Sadakane

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2018.27.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • approximation algorithm
  • dynamic algorithm
  • primal-dual
  • vertex cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G=(V,E), which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O(log n / epsilon) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem.

Cite As Get BibTex

Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao, and Kunihiko Sadakane. An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.27

Author Details

Hao-Ting Wei
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan
Wing-Kai Hon
  • Department of Computer Science, National Tsing Hua University, Hsinchu 30013, Taiwan
Paul Horn
  • Department of Mathematics, University of Denver, Denver, USA
Chung-Shou Liao
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan
Kunihiko Sadakane
  • Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan

Funding

  • Horn, Paul: Supported by NSA Young Investigator Grant H98230-15-1-0258, and Simons Collaboration Grant #525039.
  • Liao, Chung-Shou: Supported by MOST Taiwan under Grants MOST105-2628-E-007-010-MY3 and MOST105-2221-E-007-085-MY3.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact