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

DOI10.1016/J.ORL.2021.06.017MaRDI QIDQ2060337zbMATH OpenOpenAlexFDO

Authors Trung Thanh Nguyen, Khaled 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

binary non-linear programconvex programlow-rank functionpolynomial-time approximation scheme

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• An FPTAS for optimizing a class of low-rank functions over a polytope
• Approximation Schemes for Low-rank Binary Matrix Approximation Problems
• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set
• A PTAS for ℓ_p-Low Rank Approximation

Cites work

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

Cited in

(1)

• Optimization on the Euclidean unit sphere

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

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