A PTAS for a class of binary non-linear programs with low-rank functions

DOI10.1016/j.orl.2021.06.017OpenAlexW3180342608MaRDI QIDQ2060337

Trung Thanh Nguyen, Khaled M. Elbassioni

Publication date: 13 December 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2021.06.017

zbMATH Keywords

convex programpolynomial-time approximation schemebinary non-linear programlow-rank function

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (1)

Optimization on the Euclidean Unit Sphere

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An FPTAS for optimizing a class of low-rank functions over a polytope
• A review of piecewise linearization methods
• There is no EPTAS for two-dimensional knapsack
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• A PTAS for capacitated sum-of-ratios optimization
• Semidefinite representation of convex sets
• Polymatroids and mean-risk minimization in discrete optimization
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Geometric algorithms and combinatorial optimization
• The quadratic 0-1 knapsack problem with series-parallel support
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Approximating a class of combinatorial problems with rational objective function
• Fractional programming: The sum-of-ratios case
• Approximation Schemes for Multi-objective Optimization with Quadratic Constraints of Fixed CP-Rank
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Packing Under Convex Quadratic Constraints
• A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One

This page was built for publication: A PTAS for a class of binary non-linear programs with low-rank functions