An FPTAS for optimizing a class of low-rank functions over a polytope

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

zbMATH Keywords

combinatorial optimizationnonconvex 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 (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

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

This page was built for publication: An FPTAS for optimizing a class of low-rank functions over a polytope