Approximating integer quadratic programs and MAXCUT in subdense graphs
(2005) In Lecture Notes in Computer Science 3669. p.839849 Abstract
 Let A be a real symmetric n x nmatrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1vector. We present an algorithm finding approximate solutions to min x*(Ax+b) and maxx*(Ax+b) over x is an element of {1,1}(n), with an absolute error of at most (c(1) vertical bar lambda(1)vertical bar +vertical bar lambda([c2 log n])vertical bar)2n + O(alpha n + beta) root n log n), where alpha and beta are the largest absolute values of the entries in A and b, respectively, for any positive constants c1 and c2, in time polynomial in n. We demonstrate that the algorithm yields a PTAS for MAXCUT in regular graphs on n vertices of degree d of omega(root n log n), as long as they contain O(d(4) log n)... (More)
 Let A be a real symmetric n x nmatrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1vector. We present an algorithm finding approximate solutions to min x*(Ax+b) and maxx*(Ax+b) over x is an element of {1,1}(n), with an absolute error of at most (c(1) vertical bar lambda(1)vertical bar +vertical bar lambda([c2 log n])vertical bar)2n + O(alpha n + beta) root n log n), where alpha and beta are the largest absolute values of the entries in A and b, respectively, for any positive constants c1 and c2, in time polynomial in n. We demonstrate that the algorithm yields a PTAS for MAXCUT in regular graphs on n vertices of degree d of omega(root n log n), as long as they contain O(d(4) log n) 4cycles. The strongest previous result showed that Omega(n/log n) average degree graphs admit a PTAS. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/210694
 author
 Björklund, Andreas ^{LU}
 organization
 publishing date
 2005
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Lecture Notes in Computer Science
 volume
 3669
 pages
 839  849
 publisher
 Springer
 external identifiers

 wos:000233893100074
 scopus:27144556620
 ISSN
 16113349
 language
 English
 LU publication?
 yes
 id
 106ab54c614e46d89946a5b507fb31ac (old id 210694)
 date added to LUP
 20070802 12:16:18
 date last changed
 20180107 06:26:12
@article{106ab54c614e46d89946a5b507fb31ac, abstract = {Let A be a real symmetric n x nmatrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1vector. We present an algorithm finding approximate solutions to min x*(Ax+b) and maxx*(Ax+b) over x is an element of {1,1}(n), with an absolute error of at most (c(1) vertical bar lambda(1)vertical bar +vertical bar lambda([c2 log n])vertical bar)2n + O(alpha n + beta) root n log n), where alpha and beta are the largest absolute values of the entries in A and b, respectively, for any positive constants c1 and c2, in time polynomial in n. We demonstrate that the algorithm yields a PTAS for MAXCUT in regular graphs on n vertices of degree d of omega(root n log n), as long as they contain O(d(4) log n) 4cycles. The strongest previous result showed that Omega(n/log n) average degree graphs admit a PTAS.}, author = {Björklund, Andreas}, issn = {16113349}, language = {eng}, pages = {839849}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Approximating integer quadratic programs and MAXCUT in subdense graphs}, volume = {3669}, year = {2005}, }