Approximating integer quadratic programs and MAXCUT in subdense graphs
(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:
https://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
- 1611-3349
- language
- English
- LU publication?
- yes
- id
- 106ab54c-614e-46d8-9946-a5b507fb31ac (old id 210694)
- date added to LUP
- 2016-04-01 12:37:35
- date last changed
- 2022-01-27 07:39:27
@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}},
}