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

DOI10.1007/S10107-009-0287-4MaRDI QIDQ623370zbMATH OpenOpenAlexFDO

Authors Vineet Goyal, Latife Genc-Kaya, R. Ravi

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

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

Recommendations

• Quadratic programming and combinatorial minimum weight product problems
• Quadratic Programming and Combinatorial Minimum Weight Product Problems
• A FPTAS for a class of linear multiplicative problems
• An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set

Cites work

• scientific article; zbMATH DE number 3804333 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Approximation Schemes for the Restricted Shortest Path Problem
• 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

Cited in

(21)

• The Rank-One Quadratic Assignment Problem
• An efficient global optimization algorithm for a class of linear multiplicative problems based on convex relaxation
• A FPTAS for a class of linear multiplicative problems
• Global optimization algorithm for solving linear multiplicative programming problems
• Improved branch and bound algorithm and an interpolation-based search algorithm for quadratic minimization with one negative eigenvalue
• A new branch and bound method for solving linear multiplicative programming problems
• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Globally minimizing a class of linear multiplicative forms via simplicial branch-and-bound
• Outer space branch and bound algorithm for solving linear multiplicative programming problems
• Differential approximation schemes for half-product related functions and their scheduling applications
• Fast heuristics and approximation algorithms
• Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
• Linear decomposition approach for a class of nonconvex programming problems
• Solving a class of generalized fractional programming problems using the feasibility of linear programs
• An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
• Quadratic Programming and Combinatorial Minimum Weight Product Problems
• Combinatorial optimization with interaction costs: complexity and solvable cases
• An FPTAS for optimizing a class of low-rank functions over a polytope
• New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
• A class of exponential neighbourhoods for the quadratic travelling salesman problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623370)