A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

DOI10.1016/j.ejor.2011.10.049zbMath1244.90202OpenAlexW2020203251MaRDI 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 schedulingcombinatorial optimizationFPTASquadratic knapsackstrongly polynomial time

Mathematics Subject Classification ID

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

Related Items (12)

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Approximation of the Quadratic Knapsack Problem ⋮ 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 ⋮ On the rectangular knapsack problem ⋮ Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines ⋮ On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem ⋮ Differential approximation schemes for half-product related functions and their scheduling applications ⋮ 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

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.

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