Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.11851/2019
Full metadata record
DC FieldValueLanguage
dc.contributor.authorÇaşkurlu, Buğra-
dc.contributor.authorMkrtchyan, V.-
dc.contributor.authorParekh, O-
dc.contributor.authorSubramani, Kiruba Sankaran-
dc.date.accessioned2019-07-10T14:42:46Z
dc.date.available2019-07-10T14:42:46Z
dc.date.issued2014
dc.identifier.citationCaskurlu, 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.en_US
dc.identifier.issn3029743
dc.identifier.urihttps://link.springer.com/chapter/10.1007%2F978-3-662-44602-7_2-
dc.identifier.urihttps://hdl.handle.net/20.500.11851/2019-
dc.description8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science
dc.description.abstractGraphs 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.en_US
dc.language.isoenen_US
dc.publisherSpringer Verlagen_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectApproximation algorithmen_US
dc.subjectAlgorithmsen_US
dc.subjectparallel repetitionen_US
dc.titleOn Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphsen_US
dc.typeConference Objecten_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.volume8705
dc.identifier.startpage13
dc.identifier.endpage26
dc.authorid0000-0002-4647-205X-
dc.identifier.scopus2-s2.0-84906761681en_US
dc.institutionauthorÇaşkurlu, Buğra-
dc.identifier.doi10.1007/978-3-662-44602-7_2-
dc.authorscopusid35104543000-
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.identifier.scopusqualityQ2-
item.openairetypeConference Object-
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
Show simple item record



CORE Recommender

SCOPUSTM   
Citations

16
checked on Dec 21, 2024

Page view(s)

72
checked on Dec 23, 2024

Google ScholarTM

Check




Altmetric


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