Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/1167
Full metadata record
DC FieldValueLanguage
dc.contributor.authorÇaşkurlu, Buğra-
dc.contributor.authorMkrtchyan, Vahan-
dc.contributor.authorParekh, Ojas-
dc.contributor.authorSubramani, Kiruba Sankaran-
dc.date.accessioned2019-06-26T07:40:35Z
dc.date.available2019-06-26T07:40:35Z
dc.date.issued2017
dc.identifier.citationCaskurlu, B., Mkrtchyan, V., Parekh, O., & Subramani, K. (2017). Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs. SIAM Journal on Discrete Mathematics, 31(3), 2172-2184.en_US
dc.identifier.issn0895-4801
dc.identifier.urihttps://epubs.siam.org/doi/10.1137/15M1054328-
dc.identifier.urihttps://hdl.handle.net/20.500.11851/1167-
dc.description.abstractIn this paper, we study two closely related problems on bipartite graphs, viz., the partial vertex cover problem and the budgeted maximum coverage problem. Both these problems arise in a number of different application domains, including, but not limited to, computer security and transportation logistics. It is well known that the vertex cover problem is solvable in polynomial time on bipartite graphs. However, the computational complexity of the partial vertex cover problem on bipartite graphs was open, thus far. In this paper, we establish that the partial vertex cover problem is NP-hard, even on bipartite graphs. Our result also establishes that the closely related budgeted maximum coverage problem is NP-hard on bipartite graphs. For the latter problem, we present an 8/9-approximation algorithm. Our approximation guarantee matches and resolves the integrality gap of the natural linear programming relaxation for this problem and improves upon a recent 4/5-approximation algorithm for the same problem.en_US
dc.language.isoenen_US
dc.publisherSIAM Publicationsen_US
dc.relation.ispartofSiam Journal On Discrete Mathematicsen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectVertex Coveren_US
dc.subjectPartial Vertex Coveren_US
dc.subjectBudgeted Maximum Coverage Problemen_US
dc.subjectNp-Completenessen_US
dc.subjectApproximation Algorithmen_US
dc.titlePartial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphsen_US
dc.typeArticleen_US
dc.departmentFaculties, Faculty of Engineering, Department of Computer Engineeringen_US
dc.departmentFakülteler, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümütr_TR
dc.identifier.volume31
dc.identifier.issue3
dc.identifier.startpage2172
dc.identifier.endpage2184
dc.identifier.wosWOS:000412161100036en_US
dc.identifier.scopus2-s2.0-85031731610en_US
dc.institutionauthorÇaşkurlu, Buğra-
dc.identifier.doi10.1137/15M1054328-
dc.authorscopusid35104543000-
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.relation.otherAir Force of Scientific Research [FA9550-12-1-0199]; National Science Foundation [CNS-0849735, CCF-0827397, CCF-1305054]; U.S. Department of Energy's National Nuclear Security Administration [DEAC04-94AL85000]en_US
dc.identifier.scopusqualityQ2-
item.openairetypeArticle-
item.languageiso639-1en-
item.grantfulltextnone-
item.fulltextNo Fulltext-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.cerifentitytypePublications-
crisitem.author.dept02.1. Department of Artificial Intelligence Engineering-
Appears in Collections:Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection
Show simple item record



CORE Recommender

SCOPUSTM   
Citations

5
checked on Dec 21, 2024

WEB OF SCIENCETM
Citations

9
checked on Dec 21, 2024

Page view(s)

224
checked on Dec 23, 2024

Google ScholarTM

Check




Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.