Advanced

Approximating integer quadratic programs and MAXCUT in subdense graphs

Björklund, Andreas LU (2005) In Lecture Notes in Computer Science 3669. p.839-849
Abstract
Let A be a real symmetric n x n-matrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1-vector. 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 n-matrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1-vector. 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) 4-cycles. 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:
author
organization
publishing date
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
1611-3349
language
English
LU publication?
yes
id
106ab54c-614e-46d8-9946-a5b507fb31ac (old id 210694)
date added to LUP
2007-08-02 12:16:18
date last changed
2017-01-01 05:18:41
@article{106ab54c-614e-46d8-9946-a5b507fb31ac,
  abstract     = {Let A be a real symmetric n x n-matrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1-vector. 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) 4-cycles. The strongest previous result showed that Omega(n/log n) average degree graphs admit a PTAS.},
  author       = {Björklund, Andreas},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {839--849},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science},
  title        = {Approximating integer quadratic programs and MAXCUT in subdense graphs},
  volume       = {3669},
  year         = {2005},
}