A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

DOI10.1016/J.EJOR.2011.10.049MaRDI QIDQ439504zbMATH OpenOpenAlexFDO

Authors Zhou Xu

Publication date 16 August 2012

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2011.10.049

zbMATH Keywords

combinatorial optimizationFPTASquadratic knapsackmachine schedulingstrongly polynomial time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Publication:4941826
• A new fully polynomial time approximation scheme for the Knapsack problem
• Quadratic bottleneck knapsack problems

Cites work

• scientific article; zbMATH DE number 5345853 (Why is no real title available?)
• A faster fully polynomial approximation scheme for the single-machine total tardiness problem
• A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure
• A single-item economic lot-sizing problem with a non-uniform resource: Approximation
• An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure
• An FPTAS for a supply scheduling problem with non-monotone cost functions
• Batching and scheduling in a multi-machine flow shop
• Capacitated two-parallel machines scheduling to minimize sum of job completion times
• Combinatorial optimization. Theory and algorithms.
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Improving the complexities of approximation algorithms for optimization problems
• Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
• Positive half-products and scheduling with controllable processing times
• Preemptive scheduling with availability constraints to minimize total weighted completion times

Cited in

(15)

• Maximizing total tardiness on a single machine in O(n^2) time via a reduction to half-product minimization
• 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
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem
• Differential approximation schemes for half-product related functions and their scheduling applications
• On the rectangular knapsack problem
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
• Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Approximation of the quadratic knapsack problem
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications

This page was built for publication: A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

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