{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:11:19Z","timestamp":1726409479045},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_4","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T04:16:59Z","timestamp":1477801019000},"page":"49-61","source":"Crossref","is-referenced-by-count":0,"title":["Approximation and Hardness Results for the Max k-Uncut Problem"],"prefix":"10.1007","author":[{"given":"Peng","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinghe","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $$O(\\sqrt{\\log n})$$ approximation algorithms for min uncut, min 2CNF deletion, and directed cut problems. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 573\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"4_CR2","unstructured":"Alon, N., Arora, S., Manokaran, R., Moshkovitz, D., Weinstein, O.: Inapproximability of densest $$\\kappa $$ -subgraph from average case hardness. Manuscript (2011)"},{"issue":"3","key":"4_CR3","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability \u2013 towards tight results. SIAM J. Comput. 27(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $$O(n^{1\/4})$$ approximation for densest $$k$$ -subgraph. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J., Schwartz, R.: Simplex partitioning via exponential clocks and the multiway cut problem. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 535\u2013544 (2013)","DOI":"10.1145\/2488608.2488675"},{"issue":"3","key":"4_CR6","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"4_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1080\/02331934.2011.592527","volume":"61","author":"S Choudhurya","year":"2012","unstructured":"Choudhurya, S., Gaurb, D.R., Krishnamurtic, R.: An approximation algorithm for max $$k$$ -uncut with capacity constraints. Optimization 61(2), 143\u2013150 (2012)","journal-title":"Optimization"},{"key":"4_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, Crowds, and Markets: Reasoning About a Highly Connected World","author":"D Easley","year":"2010","unstructured":"Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense $$k$$ -subgraph problem. Algorithmica 29, 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for max $$k$$ -cut and max bisection. Algorithmica 18, 67\u201381 (1997)","journal-title":"Algorithmica"},{"issue":"6","key":"4_CR11","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"1","key":"4_CR12","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.: A polynomial algorithm for the $$k$$ -cut problem for fixed $$k$$ . Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1 - \\epsilon }$$ . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/11830924_18","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M Langberg","year":"2006","unstructured":"Langberg, M., Rabani, Y., Swamy, C.: Approximation algorithms for graph homomorphism problems. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX\/RANDOM -2006. LNCS, vol. 4110, pp. 176\u2013187. Springer, Heidelberg (2006). doi: 10.1007\/11830924_18"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.: Finding $$k$$ -cuts within twice the optimal. SIAM J. Comput. 24, 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-319-08783-2_28","volume-title":"Computing and Combinatorics","author":"C Wu","year":"2014","unstructured":"Wu, C., Xu, D., Du, D., Xu, W.: A complex semidefinite programming rounding approximation algorithm for the balanced max-3-uncut problem. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds.) COCOON 2014. LNCS, vol. 8591, pp. 324\u2013335. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-08783-2_28"},{"issue":"1","key":"4_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1023\/A:1021390231133","volume":"25","author":"Y Ye","year":"2003","unstructured":"Ye, Y., Zhang, J.: Approximation of dense- $$n\/2$$ -subgraph and the complement of min-bisection. J. Global Optim. 25(1), 55\u201373 (2003)","journal-title":"J. Global Optim."},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-319-21398-9_13","volume-title":"Computing and Combinatorics","author":"P Zhang","year":"2015","unstructured":"Zhang, P., Jiang, T., Li, A.: Improved approximation algorithms for the maximum happy vertices and edges problems. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 159\u2013170. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-21398-9_13"},{"key":"4_CR21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.tcs.2015.06.003","volume":"593","author":"P Zhang","year":"2015","unstructured":"Zhang, P., Li, A.: Algorithmic aspects of homophyly of networks. Theoret. Comput. Sci. 593, 117\u2013131 (2015)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T00:40:39Z","timestamp":1568508039000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}