A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
DOI10.1016/J.EJOR.2011.10.049zbMATH Open1244.90202OpenAlexW2020203251MaRDI QIDQ439504FDOQ439504
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
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
Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Positive half-products and scheduling with controllable processing times
- Title not available (Why is that?)
- Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
- Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
- Combinatorial optimization. Theory and algorithms.
- Preemptive scheduling with availability constraints to minimize total weighted completion times
- Batching and scheduling in a multi-machine flow shop
- Capacitated two-parallel machines scheduling to minimize sum of job completion times
- Improving the complexities of approximation algorithms for optimization problems
- An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure
- 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 supply scheduling problem with non-monotone cost functions
- A faster fully polynomial approximation scheme for the single-machine total tardiness problem
Cited In (14)
- 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
- Approximation of the Quadratic Knapsack Problem
- 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
- Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
- Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic 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)
