Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.11851/1167
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Çaşkurlu, Buğra | - |
dc.contributor.author | Mkrtchyan, Vahan | - |
dc.contributor.author | Parekh, Ojas | - |
dc.contributor.author | Subramani, Kiruba Sankaran | - |
dc.date.accessioned | 2019-06-26T07:40:35Z | |
dc.date.available | 2019-06-26T07:40:35Z | |
dc.date.issued | 2017 | |
dc.identifier.citation | Caskurlu, 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.issn | 0895-4801 | |
dc.identifier.uri | https://epubs.siam.org/doi/10.1137/15M1054328 | - |
dc.identifier.uri | https://hdl.handle.net/20.500.11851/1167 | - |
dc.description.abstract | In 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.iso | en | en_US |
dc.publisher | SIAM Publications | en_US |
dc.relation.ispartof | Siam Journal On Discrete Mathematics | en_US |
dc.rights | info:eu-repo/semantics/closedAccess | en_US |
dc.subject | Vertex Cover | en_US |
dc.subject | Partial Vertex Cover | en_US |
dc.subject | Budgeted Maximum Coverage Problem | en_US |
dc.subject | Np-Completeness | en_US |
dc.subject | Approximation Algorithm | en_US |
dc.title | Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs | en_US |
dc.type | Article | en_US |
dc.department | Faculties, Faculty of Engineering, Department of Computer Engineering | en_US |
dc.department | Fakülteler, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü | tr_TR |
dc.identifier.volume | 31 | |
dc.identifier.issue | 3 | |
dc.identifier.startpage | 2172 | |
dc.identifier.endpage | 2184 | |
dc.identifier.wos | WOS:000412161100036 | en_US |
dc.identifier.scopus | 2-s2.0-85031731610 | en_US |
dc.institutionauthor | Çaşkurlu, Buğra | - |
dc.identifier.doi | 10.1137/15M1054328 | - |
dc.authorscopusid | 35104543000 | - |
dc.relation.publicationcategory | Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı | en_US |
dc.relation.other | Air 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.scopusquality | Q2 | - |
item.openairetype | Article | - |
item.languageiso639-1 | en | - |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
crisitem.author.dept | 02.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 |
CORE Recommender
SCOPUSTM
Citations
5
checked on Dec 21, 2024
WEB OF SCIENCETM
Citations
9
checked on Dec 21, 2024
Page view(s)
222
checked on Dec 16, 2024
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.