Quadratic programming and combinatorial minimum weight product problems

DOI10.1007/s10107-006-0047-7zbMath1203.90120MaRDI QIDQ985315

Gerhard J. Woeginger, Walter Kern

Publication date: 21 July 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0047-7

zbMATH Keywords

quadratic programming; shortest path; approximation scheme

Mathematics Subject Classification ID

90C20: Quadratic programming

Related Items

An FPTAS for optimizing a class of low-rank functions over a polytope, Linear decomposition approach for a class of nonconvex programming problems, Approximation of linear fractional-multiplicative problems, An FPTAS for minimizing the product of two non-negative linear cost functions, Differential approximation schemes for half-product related functions and their scheduling applications, A FPTAS for a class of linear multiplicative problems, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, Analysis of FPTASes for the multi-objective shortest path problem, A characterization of linearizable instances of the quadratic minimum spanning tree problem, Approximation algorithm for a class of global optimization problems

Cites Work

• Approximation algorithms for indefinite quadratic programming
• Quadratic programming with one negative eigenvalue is NP-hard
• Generalized concavity
• Polynomial algorithms for a class of minimum rank-two cost path problems
• Combinatorial Optimization with Rational Objective Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item