An FPTAS for minimizing the product of two non-negative linear cost functions
DOI10.1007/S10107-009-0287-4zbMATH Open1206.90112OpenAlexW2161103838MaRDI QIDQ623370FDOQ623370
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
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
Quadratic programming (90C20) Multi-objective and goal programming (90C29) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27)
Cites Work
- Title not available (Why is that?)
- Approximation Schemes for the Restricted Shortest Path Problem
- Title not available (Why is that?)
- Approximation algorithms for indefinite quadratic programming
- Quadratic programming with one negative eigenvalue is NP-hard
- \(NP\)-hardness of linear multiplicative programming and related problems
- Quadratic programming and combinatorial minimum weight product problems
Cited In (16)
- The Rank-One Quadratic Assignment Problem
- An efficient global optimization algorithm for a class of linear multiplicative problems based on convex relaxation
- Fast Heuristics and Approximation Algorithms
- Global optimization algorithm for solving linear multiplicative programming problems
- 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
- 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
- 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)
