Show simple item record

dc.contributor.authorÇaşkurlu, Buğra
dc.contributor.authorMkrtchyan, V.
dc.contributor.authorParekh, O
dc.contributor.authorSubramani, K.
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.urihttp://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.isoengen_US
dc.publisherSpringer Verlagen_US
dc.rightsinfo:eu-repo/semantics/closedAccess
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.typeconferenceObjecten_US
dc.relation.journalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.contributor.departmentTOBB ETU, Faculty of Engineering, Department of Computer Engineeringen_US
dc.contributor.departmentTOBB ETÜ, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümütr_TR
dc.identifier.volume8705
dc.identifier.startpage13
dc.identifier.endpage26
dc.identifier.scopus2-s2.0-84906761681
dc.contributor.tobbetuauthorÇaşkurlu, Buğra
dc.contributor.YOKid56295
dc.identifier.doi10.1007/978-3-662-44602-7_2
dc.contributor.ScopusAuthorID35104543000
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıtr_TR


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record