Parameterized Integer Quadratic Programming: Variables and Coefficients

2015/11/01 by Daniel Lokshtanov, Lokshtanov, Daniel · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1511.00310

openalex publication_date 2015/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the Integer Quadratic Programming problem input is an n*n integer matrix Q, an m*n integer matrix A and an m-dimensional integer vector b. The task is to find a vector x in Zⁿ, minimizing x^TQx, subject to Ax <= b. We give a fixed parameter tractable algorithm for Integer Quadratic Programming parameterized by n+a. Here a is the largest absolute value of an entry of Q and A. As an application of our main result we show that Optimal Linear Arrangement is fixed parameter tractable parameterized by the size of the smallest vertex cover of the input graph. This resolves an open problem from the recent monograph by Downey and Fellows.

Cited by

• Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
• Integer Programming in Parameterized Complexity: Three Miniatures

Related

• An Algorithmic Theory of Integer Programming
• Integer Programming and Incidence Treedepth
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
• Integer Programming in Parameterized Complexity: Three Miniatures
• Integer Programming with a Fixed Number of Variables