{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T19:03:31Z","timestamp":1774638211744,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1998,2,1]],"date-time":"1998-02-01T00:00:00Z","timestamp":886291200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1998,2]]},"DOI":"10.1007\/bf01581168","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T09:38:16Z","timestamp":1114681096000},"page":"253-264","source":"Crossref","is-referenced-by-count":62,"title":["Approximating the independence number via the\u03d1-function"],"prefix":"10.1007","volume":"80","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Nabil","family":"Kahale","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.37236\/1192","volume":"1","author":"N. Alon","year":"1994","unstructured":"N. Alon, Explicit Ramsey graphs and orthonormal labelings,The Electronic Journal of Combinatorics 1 (1994) R12.","journal-title":"The Electronic Journal of Combinatorics"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01903803","volume":"57","author":"N. Alon","year":"1991","unstructured":"N. Alon and Y. Peres, Euclidean Ramsey theory and a construction of Bourgain,Acta Mathematica Hungarica 57 (1991) 61\u201364.","journal-title":"Acta Mathematica Hungarica"},{"key":"CR3","first-page":"14","volume-title":"Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science","author":"S. Arora","year":"1992","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and intractability of approximation problems, in:Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1992) 14\u201323."},{"key":"CR4","first-page":"2","volume-title":"Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science","author":"S. Arora","year":"1992","unstructured":"S. Arora and S. Safra, Probabilistic checking of proofs; a new characterization of NP, in:Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1992) 2\u201313."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/BF01840398","volume":"5","author":"B. Berger","year":"1990","unstructured":"B. Berger and J. Rompel, A better performance guarantee for approximate graph coloring,Algorithmica 5 (1990) 459\u2013466.","journal-title":"Algorithmica"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger, On the complexity of approximating the independent set problem,Information and Computation 96 (1992) 77\u201394.","journal-title":"Information and Computation"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. Boppana","year":"1992","unstructured":"R. Boppana and M.M. Halldorsson, Approximating maximum independent sets by excluding subgraphs,BIT 32 (1992) 180\u2013196.","journal-title":"BIT"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"253","DOI":"10.4064\/cm-16-1-253-256","volume":"16","author":"P. Erd\u00f6s","year":"1967","unstructured":"P. Erd\u00f6s, Some remarks on chromatic graphs,Colloquium Mathematicum 16 (1967) 253\u2013256.","journal-title":"Colloquium Mathematicum"},{"key":"CR9","first-page":"463","volume":"2","author":"P. Erd\u00f6s","year":"1935","unstructured":"P. Erd\u00f6s and G. Szekeres, A combinatorial problem in geometry,Compositio Mathematica 2 (1935) 463\u2013470.","journal-title":"Compositio Mathematica"},{"key":"CR10","first-page":"635","volume-title":"27th Annual ACM Symposium on Theory of Computing","author":"U. Feige","year":"1995","unstructured":"U. Feige, Randomized graph products, chromatic numbers, and the Lov\u00e1sz\u03d1-function, in:27th Annual ACM Symposium on Theory of Computing (ACM Press, New York, 1995) 635\u2013640."},{"key":"CR11","first-page":"2","volume-title":"Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science","author":"U. Feige","year":"1991","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra and M. Szegedy, Approximating Clique is almost NP-complete, in:Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1991) 2\u201312."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1090\/S0002-9947-1987-0871675-6","volume":"300","author":"P. Frankl","year":"1987","unstructured":"P. Frankl and V. R\u00f6dl, Forbidden intersections,Transactions AMS 300 (1987) 259\u2013286.","journal-title":"Transactions AMS"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,Journal ACM 42 (1995) 1115\u20131145.","journal-title":"Journal ACM"},{"key":"CR14","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1989","unstructured":"G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, 1989)."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halldorsson","year":"1993","unstructured":"M.M. Halldorsson, A still better performance guarantee for approximate graph coloring,Information Processing Letters 45 (1993) 19\u201323.","journal-title":"Information Processing Letters"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is hard to approximate withinn 1-\u03b5,Proc. 37th IEEE FOCS (IEEE, 1996) 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,Combinatorica 1 (1981) 169\u2013197.","journal-title":"Combinatorica"},{"key":"CR18","first-page":"2","volume-title":"35th Symposium on Foundations of Computer Science","author":"D. Karger","year":"1994","unstructured":"D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semi-definite programming, in:35th Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994) 2\u201313."},{"key":"CR19","volume-title":"Reducibility among combinatorial problems","author":"R. Karp","year":"1972","unstructured":"R. Karp,Reducibility among combinatorial problems, eds. Miller and Thatcher (Plenum Press, New York, 1972)."},{"key":"CR20","first-page":"64","volume":"157","author":"B.S. Kashin","year":"1981","unstructured":"B.S. Kashin and S.V. Konyagin, On systems of vectors in a Hilbert space,Trudy Mat. Inst. imeni V.A. Steklova 157 (1981) 64\u201367. English translation in:Proceedings of the Steklov Institute of Mathematics (AMS, 1983) 67\u201370.","journal-title":"Trudy Mat. Inst. imeni V.A. Steklova"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, The sandwich theorem,The Electronic Journal of Combinatorics 1 (A1) (1994).","DOI":"10.37236\/1193"},{"key":"CR22","first-page":"63","volume":"29","author":"S.V. Konyagin","year":"1981","unstructured":"S.V. Konyagin, Systems of vectors in Euclidean space and an extremal problem for polynomials,Mat. Zametki 29 (1981) 63\u201374. English translation in:Mathematical Notes of the Academy of the USSR 29 (1981) 33\u201339.","journal-title":"Mat. Zametki"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On the Shannon capacity of a graph,IEEE Transactions on Information Theory 25 (1979) 1\u20137.","journal-title":"IEEE Transactions on Information Theory"},{"key":"CR24","first-page":"36","volume-title":"35th Symposium on Foundations of Computer Science","author":"M. Szegedy","year":"1994","unstructured":"M. Szegedy, A note on the\u03d1 number of Lov\u00e1sz and the generalized Delsarte bound, in:35th Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994) 36\u201339."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581168.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01581168\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,31]],"date-time":"2024-12-31T23:28:44Z","timestamp":1735687724000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01581168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,2]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,2]]}},"alternative-id":["BF01581168"],"URL":"https:\/\/doi.org\/10.1007\/bf01581168","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,2]]}}}