An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

DOI10.1137/1.9781611974331.ch118zbMath1411.68191arXiv1507.00969OpenAlexW2950038749MaRDI QIDQ4575702

Robert Hildebrand, Kevin Zemmer, Robert Weismantel

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.00969

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation algorithms (68W25)

Related Items (8)

Provable randomized rounding for minimum-similarity diversification ⋮ Short Presburger Arithmetic Is Hard ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Complexity of optimizing over the integers ⋮ An approximation algorithm for indefinite mixed integer quadratic programming ⋮ Subdeterminants and Concave Integer Quadratic Programming ⋮ On approximation algorithms for concave mixed-integer quadratic programming ⋮ Electrical flows over spanning trees

This page was built for publication: An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra