Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.11851/2019
Title: | On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs | Authors: | Çaşkurlu, Buğra Mkrtchyan, V. Parekh, O Subramani, Kiruba Sankaran |
Keywords: | Approximation algorithm Algorithms parallel repetition |
Publisher: | Springer Verlag | Source: | Caskurlu, B., Williamson, M., Subramani, K., & Mkrtchyan, V. (2018). On approximating optimal weight “no”-certificates in weighted difference constraint systems. Journal of Combinatorial Optimization, 36(2), 329-345. | Abstract: | Graphs are often used to model risk management in various systems. Particularly, Caskurlu et al. in [6] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Coverproblem on bipartite graphs. It is well-known that the vertex cover problem is in P on bipartite graphs; however, the computational complexity of the partial vertex cover problem on bipartite graphs is open. In this paper, we show that the partial vertex cover problem is NP-hard on bipartite graphs. Then, we show that the budgeted maximum coverage problem (a problem related to partial vertex cover problem) admits an 8/9-approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation. © 2014 IFIP International Federation for Information Processing. | Description: | 8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science | URI: | https://link.springer.com/chapter/10.1007%2F978-3-662-44602-7_2 https://hdl.handle.net/20.500.11851/2019 |
ISSN: | 3029743 |
Appears in Collections: | Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection |
Show full item record
CORE Recommender
SCOPUSTM
Citations
16
checked on Sep 7, 2024
Page view(s)
68
checked on Sep 2, 2024
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.