A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
From MaRDI portal
Publication:439504
DOI10.1016/j.ejor.2011.10.049zbMath1244.90202MaRDI QIDQ439504
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
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, 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.
