Du är här

Approximating integer quadratic programs and MAXCUT in subdense graphs

Publiceringsår: 2005
Språk: Engelska
Sidor: 839-849
Publikation/Tidskrift/Serie: Lecture notes in computer science. Algorithmis - ESA 2005
Volym: 3669
Dokumenttyp: Artikel
Förlag: Springer


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.



  • Technology and Engineering


  • ISSN: 0302-9743

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen