{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T17:26:43Z","timestamp":1794590803598,"version":"4.9.1"},"reference-count":3,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Trevisan [SIAM J. Comput., 41 (2012), pp. 1769--1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1\/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general maximum colored cut problem.<\/jats:p>","DOI":"10.1137\/14099098x","type":"journal-article","created":{"date-parts":[[2015,2,3]],"date-time":"2015-02-03T15:40:19Z","timestamp":1422978019000},"page":"259-268","source":"Crossref","is-referenced-by-count":16,"title":["Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning"],"prefix":"10.1137","volume":"29","author":[{"given":"Jos\u00e9 A.","family":"Soto","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"E. Beckenbach and R. Bellman,\n                      An Introduction to Inequalities\n                      , Random House, New York, 1961.","DOI":"10.5948\/UPO9780883859216"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/090773714"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14099098X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:55Z","timestamp":1787319415000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14099098X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":3,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/14099098X"],"URL":"https:\/\/doi.org\/10.1137\/14099098x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}