Maximum cut problem: new models

Basit Öğe Kaydı
dc.authoridKutucu, Hakan/0000-0001-7144-7246
dc.contributor.authorKutucu, Hakan
dc.contributor.authorSharifov, Firdovsi
dc.date.accessioned2024-09-29T16:04:42Z
dc.date.available2024-09-29T16:04:42Z
dc.date.issued2020
dc.departmentKarabük Üniversitesien_US
dc.description.abstractThe maximum cut problem is known to be NP-hard, and consists in determining a partition of the vertices of a given graph such that the sum of the weights of the edges having one end node in each set is maximum. In this paper, we formulate the maximum cut problem as a maximization of a simple non-smooth convex function over the convex hull of bases of the polymatroid associated with a submodular function defined on the subsets of vertices of a given graph. In this way, we show that a greedy-like algorithm with O(mn(2)) time complexity finds a base of a polymatroid that is a solution to the maximum cut problem with different approximation ratio. Moreover, with respect to a base of a polymatroid, we formulate the maximum cut problem as a maximum flow problem between a source and a sink. We then investigate the necessary and sufficient conditions on the optimality of the base in terms of network flow.en_US
dc.identifier.doi10.11121/ijocta.01.2020.00826
dc.identifier.endpage112en_US
dc.identifier.issn2146-0957
dc.identifier.issn2146-5703
dc.identifier.issue1en_US
dc.identifier.scopus2-s2.0-85091087664en_US
dc.identifier.scopusqualityQ3en_US
dc.identifier.startpage104en_US
dc.identifier.trdizinid378109en_US
dc.identifier.urihttps://doi.org/10.11121/ijocta.01.2020.00826
dc.identifier.urihttps://search.trdizin.gov.tr/tr/yayin/detay/378109
dc.identifier.urihttps://hdl.handle.net/20.500.14619/6276
dc.identifier.volume10en_US
dc.identifier.wosWOS:000871121500013en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakTR-Dizinen_US
dc.language.isoenen_US
dc.publisherRamazan Yamanen_US
dc.relation.ispartofInternational Journal of Optimization and Control-Theories & Applications-Ijoctaen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectConvex functionen_US
dc.subjectBases of polymatroiden_US
dc.subjectSubmodular functionen_US
dc.subjectNetwork flowsen_US
dc.titleMaximum cut problem: new modelsen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu
TR-Dizin İndeksli Yayınlar Koleksiyonu