An approximation algorithm for scheduling two parallel machines with capacity constraints.

DOI10.1016/S0166-218X(02)00601-7zbMath1126.90031OpenAlexW2021083541MaRDI QIDQ1408454

Heng Yang, Yinyu Ye, Jia-Wei Zhang

Publication date: 22 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00601-7

zbMATH Keywords

schedulingsemidefinite programmingparallel machinesapproximation algorithmmaximum cut

Mathematics Subject Classification ID

Semidefinite programming (90C22) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Approximating Scheduling Machines with Capacity Constraints, A comment on scheduling two parallel machines with capacity constraints

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Outward rotations
• Convex quadratic and semidefinite programming relaxations in scheduling
• Algorithmic derandomization via complexity theory
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Algorithms for Scheduling Independent Tasks
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• A .699-approximation algorithm for Max-Bisection.