Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions

DOI10.1016/J.DAM.2017.06.020MaRDI QIDQ2399291zbMATH OpenOpenAlexFDO

Authors Trung Thanh Nguyen, Khaled Elbassioni

Publication date 22 August 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.06.020

zbMATH Keywords

approximation algorithmbinary packingcompletely positive ranknonnegative rankquadratic constraintsubmodular

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Multi-objective and goal programming (90C29)

Recommendations

• Packing under convex quadratic constraints
• Packing under convex quadratic constraints
• Approximation algorithm for a mixed binary quadratically constrained quadratic programming problem
• An improved lower bound and approximation algorithm for binary constrained quadratic programming problem
• Approximation Schemes for Multi-objective Optimization with Quadratic Constraints of Fixed CP-Rank

Cites work

• A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs
• A polynomial-time algorithm for computing low CP-rank decompositions
• A Selection Problem of Shared Fixed Costs and Network Flows
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An almost optimal algorithm for computing nonnegative rank
• An efficient algorithm to allocate shelf space
• An optimal convex hull algorithm in any fixed dimension
• Approximating multiobjective knapsack problems
• Approximating the quadratic knapsack problem on special graph classes
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Combinatorial auctions. Foreword by Vernon L. Smith.
• Computing a nonnegative matrix factorization -- provably
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• scientific article; zbMATH DE number 3943824 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 1305477 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Interior-point methods for optimization
• Linear-time computability of combinatorial problems on series-parallel graphs
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Min-cut clustering
• Minimization of half-products
• New results on the completion time variance minimization
• On the computational complexity of membership problems for the completely positive cone and its dual
• On the copositive representation of binary and continuous nonconvex quadratic programs
• On the parameterization of the CreditRisk\(^+\) model for estimating credit portfolio risk
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Symmetry and Approximability of Submodular Maximization Problems
• The maximum numbers of faces of a convex polytope
• The quadratic 0-1 knapsack problem with series-parallel support
• The quadratic knapsack problem -- a survey
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Topology of series-parallel networks
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(6)

• A PTAS for a class of binary non-linear programs with low-rank functions
• Packing under convex quadratic constraints
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• Packing under convex quadratic constraints
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

This page was built for publication: Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions

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