{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:12:57Z","timestamp":1725455577956},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637578"},{"type":"electronic","value":"9783540696438"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0024483","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:30:56Z","timestamp":1132385456000},"page":"2-14","source":"Crossref","is-referenced-by-count":8,"title":["Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT"],"prefix":"10.1007","author":[{"given":"Paola","family":"Alimonti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"P. Alimonti, Non-Oblivious Local Search for Graph and Hypergraph Coloring Problems, 21st International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1017, Springer Verlag, 167\u2013180, 1995.","DOI":"10.1007\/3-540-60618-1_74"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0020-0190(95)00196-4","volume":"57","author":"P. Alimonti","year":"1996","unstructured":"P. Alimonti, New Local Search Approximation Techniques for Maximum Generalized Satisfiability Problems. Information Processing Letters 57, 151\u2013158, 1996.","journal-title":"Information Processing Letters"},{"key":"2_CR3","unstructured":"P. Alimonti, and R. Ferroni, Algorithms for the Maximum Generalized Satisfiability Problem, Rapporto Tecnico, RAP 01.93, Dipartimento di Informatica e Sistemistica, Universit\u00e0 degli Studi di Roma \u201cla Sapienza\u201d, 1993."},{"issue":"4","key":"2_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1051\/ita\/1996300403051","volume":"30","author":"P. Alimonti","year":"1996","unstructured":"P. Alimonti, S. Leonardi, A. Marchetti Spaccamela, Average Case Analysis of Fully Dynamic Connectivity for Directed Graphs, RAIRO Journal on Theoretical Informatics and Applications 30, 4, 305\u2013318, 1996.","journal-title":"RAIRO Journal on Theoretical Informatics and Applications"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0743-1066(91)90006-B","volume":"10","author":"G. Ausiello","year":"1991","unstructured":"G. Ausiello, and G.F. Italiano, On-Line Algorithms for Polynomially Solvable Satisfiability Problems, Journal of Logic Programming, 10, 69\u201390, 1991.","journal-title":"Journal of Logic Programming"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/0196-6774(91)90036-X","volume":"12","author":"G. Ausiello","year":"1991","unstructured":"G. Ausiello, G.F. Italiano, A. Marchetti-Spaccamela, U. Nanni, Incremental algorithms for minimal length paths, J. of Algorithms, 12, 615\u2013638, 1991.","journal-title":"J. of Algorithms"},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(95)00006-X","volume":"54","author":"G. Ausiello","year":"1995","unstructured":"G. Ausiello, and M. Protasi, Local Search, Reducibility and Approximability of NP Optimization Problems, Information Processing Letters 54, 73\u201379, 1995.","journal-title":"Information Processing Letters"},{"key":"2_CR8","series-title":"Tech. Rep. TR-95-052","volume-title":"Reactive local search for the maximum clique problem","author":"R. Battiti","year":"1995","unstructured":"R. Battiti, M. Protasi, Reactive local search for the maximum clique problem. Tech. Rep. TR-95-052, International Computer Science Institute, Berkeley, CA, 1995."},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"D.Eppstein, Z.Galil, G.F.Italiano, A.Nissenzweig, Sparsification \u2014 a technique for speeding up dynamic graph algorithms, Proc. 33rd Annual Symp. on Foundations of Computer Science, 1992.","DOI":"10.1109\/SFCS.1992.267818"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"U. Feige, M. Goemans, Approximating the value of the two prover proof system with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israeli Symposium on Theory of Computing and Systems, 182\u2013189, 1995.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"2_CR11","volume-title":"The solution Sets of Local Search Problems","author":"S.T. Fischer","year":"1995","unstructured":"S.T. Fischer, The solution Sets of Local Search Problems, PhD Thesis, Department of Computer Science, University of Amsterdam, Amsterdam, 1995."},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"G.N. Frederickson, Data Structure for On-Line Updating of Minimum Spanning Tree with Applications, SIAM J. Comput., 14, 781\u2013798, 1985.","journal-title":"SIAM J. Comput."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"F. Glover, Tabu search, Part I, ORSA Journal of Computing, 1, 190\u2013206, 1989.","journal-title":"ORSA Journal of Computing"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"M. Goemans, and D.P. Williamson,.878-Approximation Algorithms for MAX CUT and MAX 2SAT, Proc. of the 35th Annual IEEE Conference on Foundations of Computer Science, 1994.","DOI":"10.1145\/195058.195216"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"P. Klein, H. Lu,i Efficient Approximation Algorithms for Semidefinite Programming Arising from MAX CUT and COLORING, Proc. 28th ACM Symposium on Theory of Computinga, 1996, 1996.","DOI":"10.1145\/237814.237980"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Z. Ivkovic, E.L.Lloyd, Fully Dynamic Maintenance of Vertex Cover, Proc. of the 19th International Workshop on Graph-Theoretic Concept in Computer Science, LNCS 790, 99\u2013111, 1993.","DOI":"10.1007\/3-540-57899-4_44"},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis, How Easy Is Local Search?, Journal of Computer and System Sciences, 37, 79\u2013100, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, On Syntactic versus Computational Views of Approximability, Proc. of the 35th Annual IEEE Conference on Foundations of Computer Science, 1994.","DOI":"10.1109\/SFCS.1994.365712"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"S. Kirkpatrick, C. Gelat, and M. Vecchi, Optimization by simulated annealing, Science, 220, 671\u2013680, 1983.","journal-title":"Science"},{"key":"2_CR20","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-19422-3_9","volume-title":"Proc Work. on Graph Theoretic concepts in Comp. Sci.","author":"J.A. Poutr\u00e9 La","year":"1988","unstructured":"J.A. La Poutr\u00e9, Ivan Leeuwen, Maintenance of transitive closure and transitive reduction of graphs, Proc Work. on Graph Theoretic concepts in Comp. Sci., LNCS 314, Springer Verlag, Berlin, 106\u2013120, 1988."},{"key":"2_CR21","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou, and M. Yannakakis, Optimization, Approximation, and Complexity Classes, Journal of Computer and System Sciences, 43, 425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan, Amortized Computational Complexity, SIAM J.Alg.Disc. Math., 6, 306\u2013318, 1985.","journal-title":"SIAM J.Alg.Disc. Math."},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"L.Trevisan, Positive linear programming, parallel approximation and PCP's, Proceedings 4th Annual European Symposium on Algorithms, 1996.","DOI":"10.1007\/3-540-61680-2_47"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T01:35:33Z","timestamp":1586568933000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637578","9783540696438"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/bfb0024483","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}