A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

DOI10.1016/j.ejor.2011.10.049zbMath1244.90202MaRDI QIDQ439504

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

machine scheduling; combinatorial optimization; FPTAS; quadratic knapsack; strongly polynomial time

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

68W25: Approximation algorithms

Related Items

Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines, 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, Differential approximation schemes for half-product related functions and their scheduling applications, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, An iterated ``hyperplane exploration approach for the quadratic knapsack problem, A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, On the rectangular knapsack problem, On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Approximation of the Quadratic Knapsack Problem

Cites Work

• Unnamed Item
• Batching and scheduling in a multi-machine flow shop
• A faster fully polynomial approximation scheme for the single-machine total tardiness problem
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure
• Capacitated two-parallel machines scheduling to minimize sum of job completion times
• Positive half-products and scheduling with controllable processing times
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• Improving the complexities of approximation algorithms for optimization problems
• 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
• MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
• Combinatorial optimization. Theory and algorithms.