An FPTAS for minimizing the product of two non-negative linear cost functions

DOI10.1007/S10107-009-0287-4zbMath1206.90112OpenAlexW2161103838MaRDI QIDQ623370

Latife Genc-Kaya, R. Ravi, Vineet Goyal

Publication date: 14 February 2011

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

Full work available at URL: https://doi.org/10.1007/s10107-009-0287-4

zbMATH Keywords

quadratic programmingcombinatorial optimizationapproximation schemes

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Multi-objective and goal programming (90C29) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items (14)

Solving a class of generalized fractional programming problems using the feasibility of linear programs ⋮ Fast Heuristics and Approximation Algorithms ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Global optimization algorithm for solving linear multiplicative programming problems ⋮ The Rank-One Quadratic Assignment Problem ⋮ An FPTAS for optimizing a class of low-rank functions over a polytope ⋮ Globally minimizing a class of linear multiplicative forms via simplicial branch-and-bound ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation ⋮ Linear decomposition approach for a class of nonconvex programming problems ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ Outer space branch and bound algorithm for solving linear multiplicative programming 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

• Approximation algorithms for indefinite quadratic programming
• Quadratic programming and combinatorial minimum weight product problems
• Quadratic programming with one negative eigenvalue is NP-hard
• \(NP\)-hardness of linear multiplicative programming and related problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: An FPTAS for minimizing the product of two non-negative linear cost functions