Quadratic programming and combinatorial minimum weight product problems

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

Walter Kern, Gerhard J. Woeginger

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 programmingshortest pathapproximation scheme

Mathematics Subject Classification ID

Quadratic programming (90C20)

Related Items (13)

Fast Heuristics and Approximation Algorithms ⋮ 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 ⋮ The Rank-One Quadratic Assignment Problem ⋮ An FPTAS for optimizing a class of low-rank functions over a polytope ⋮ Approximation algorithm for a class of global optimization problems ⋮ An FPTAS for minimizing the product of two non-negative linear cost functions ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ Linear decomposition approach for a class of nonconvex programming problems ⋮ Approximation of linear fractional-multiplicative problems ⋮ Differential approximation schemes for half-product related functions and their scheduling applications ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Quadratic programming and combinatorial minimum weight product problems