{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T07:52:51Z","timestamp":1772265171683,"version":"3.50.1"},"posted":{"date-parts":[[2018,12,18]]},"group-title":"PeerJ Preprints","reference-count":0,"publisher":"PeerJ","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>\n                  In the constrained max\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem on hypergraphs, we are given a weighted hypergraph\n                  <jats:italic>H=(V, E)<\/jats:italic>\n                  , an integer\n                  <jats:italic>k<\/jats:italic>\n                  and a set\n                  <jats:italic>c<\/jats:italic>\n                  of constraints. The goal is to divide the set\n                  <jats:italic>V<\/jats:italic>\n                  of vertices into\n                  <jats:italic>k<\/jats:italic>\n                  disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in\n                  <jats:italic>c<\/jats:italic>\n                  . In this paper we present a local search algorithm for the constrained max\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem on hypergraphs and show that it has approximation ratio\n                  <jats:italic>1-1\/k<\/jats:italic>\n                  for a variety of constraints\n                  <jats:italic>c<\/jats:italic>\n                  , such as for the constraints defining the max Steiner\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem, the max multiway cut problem and the max\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem. We also show that our local search algorithm can be used on the max\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem with given sizes of parts and on the capacitated max\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem, and has approximation ratio\n                  <jats:italic>\n                    1-|V\n                    <jats:sub>max<\/jats:sub>\n                    |\/|V|\n                  <\/jats:italic>\n                  , where\n                  <jats:italic>\n                    |V\n                    <jats:sub>max<\/jats:sub>\n                    |\n                  <\/jats:italic>\n                  is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem that has approximation ratio (k-1)\/(3k-2).\n                <\/jats:p>","DOI":"10.7287\/peerj.preprints.27434v1","type":"posted-content","created":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T12:53:43Z","timestamp":1545137623000},"source":"Crossref","is-referenced-by-count":0,"title":["A local search algorithm for the constrained max cut problem on hypergraphs."],"prefix":"10.7287","author":[{"given":"Nasim","family":"Samei","sequence":"first","affiliation":[{"name":"Computer Science, University of Western Ontario, London, ON, Canada"}]},{"given":"Roberto","family":"Solis-Oba","sequence":"additional","affiliation":[{"name":"Computer Science, University of Western Ontario, London, On, Canada"}]}],"member":"4443","container-title":[],"original-title":[],"link":[{"URL":"https:\/\/peerj.com\/preprints\/27434v1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/preprints\/27434v1.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/preprints\/27434v1.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/preprints\/27434v1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,23]],"date-time":"2019-12-23T20:12:05Z","timestamp":1577131925000},"score":1,"resource":{"primary":{"URL":"https:\/\/peerj.com\/preprints\/27434v1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":0,"aliases":["10.7287\/peerj.preprints.27434"],"URL":"https:\/\/doi.org\/10.7287\/peerj.preprints.27434v1","relation":{"references":[{"id-type":"doi","id":"10.7287\/peerj.preprints.27434v1\/supp-1","asserted-by":"subject"},{"id-type":"doi","id":"10.7287\/peerj.preprints.27434v1\/supp-1","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2018,12,18]]},"subtype":"preprint"}}