An FPTAS for optimizing a class of low-rank functions over a polytope
From MaRDI portal
Publication:378129
DOI10.1007/s10107-011-0511-xzbMath1280.90096OpenAlexW2007598971MaRDI QIDQ378129
Andreas S. Schulz, Shashi Mittal
Publication date: 11 November 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/76278
Nonconvex programming, global optimization (90C26) Multi-objective and goal programming (90C29) Quadratic programming (90C20) Combinatorial optimization (90C27)
Related Items (17)
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 ⋮ The Rank-One Quadratic Assignment Problem ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ (Global) optimization: historical notes and recent developments ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ Range division and linearization algorithm for a class of linear ratios optimization problems ⋮ Unnamed Item ⋮ Efficient local search procedures for quadratic fractional programming problems ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Reference points and approximation algorithms in multicriteria discrete optimization ⋮ Linear decomposition approach for a class of nonconvex programming problems ⋮ On the tightness of an LP relaxation for rational optimization and its applications ⋮ A vector linear programming approach for certain global optimization problems ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ A PTAS for a class of binary non-linear programs with low-rank functions
Cites Work
- An FPTAS for minimizing the product of two non-negative linear cost functions
- Approximation algorithms for indefinite quadratic programming
- Polymatroids and mean-risk minimization in discrete optimization
- Quadratic programming and combinatorial minimum weight product problems
- Quadratic programming with one negative eigenvalue is NP-hard
- A new reformulation-linearization technique for bilinear programming problems
- Linear multiplicative programming
- Geometric algorithms and combinatorial optimization
- Cutting plane/tabu search algorithms for low rank concave quadratic programming problems
- Handbook of global optimization
- Optimization on low rank nonconvex structures
- Multiplicative programming problems: Analysis and efficient point search heuristic
- Polynomial algorithms for a class of minimum rank-two cost path problems
- An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
- \(NP\)-hardness of linear multiplicative programming and related problems
- Fractional programming: The sum-of-ratios case
- Maximizing Non-monotone Submodular Functions
- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
- Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
- Jointly Constrained Biconvex Programming
- A cutting plane algorithm for solving bilinear programs
- A note on the sum of a linear and linear-fractional function
- Cutting Planes for Low-Rank-Like Concave Minimization Problems
- Some optimal inapproximability results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An FPTAS for optimizing a class of low-rank functions over a polytope
