Improving the complexities of approximation algorithms for optimization problems
From MaRDI portal
Publication:1904613
DOI10.1016/0167-6377(95)91591-ZzbMath0836.90097OpenAlexW2068013459MaRDI QIDQ1904613
Publication date: 7 January 1996
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(95)91591-z
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items (24)
Approximation issues of fractional knapsack with penalties: a note ⋮ A theoretical development for the total tardiness problem and its application in branch and bound algorithms ⋮ Errata and comments on ``Approximation algorithms for the capacitated plant allocation problem ⋮ Integer knapsack problems with profit functions of the same value range ⋮ Min-max and min-max (relative) regret approaches to representatives selection problem ⋮ An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand ⋮ A strongly polynomial FPTAS for the symmetric quadratic knapsack problem ⋮ Production and Transportation Integration for Commit-to-Delivery Mode with General Shipping Costs ⋮ A faster fully polynomial approximation scheme for the single-machine total tardiness problem ⋮ A single-item economic lot-sizing problem with a non-uniform resource: Approximation ⋮ An FPTAS for SM‐CELS problem with monotone cost functions ⋮ Integrated production and delivery scheduling with disjoint windows ⋮ An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure ⋮ Provision-after-wait with preferences ordered by difference: tighter complexity and better approximation ⋮ Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval ⋮ FPTAS for half-products minimization with scheduling applications ⋮ Metric approach for finding approximate solutions of scheduling problems ⋮ Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries ⋮ Single machine scheduling subject to deadlines and resource dependent processing times ⋮ The single-machine total tardiness scheduling problem: review and extensions ⋮ Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities ⋮ Batch scheduling and common due-date assignment on a single machine ⋮ Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
Cites Work
- Unnamed Item
- Fast approximation algorithm for job sequencing with deadlines
- A fully polynomial approximation scheme for the total tardiness problem
- Single Machine Scheduling to Minimize Total Late Work
- Algorithms for Scheduling Independent Tasks
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
This page was built for publication: Improving the complexities of approximation algorithms for optimization problems
