122. Improving bounds on approximation algorithms for the Triangle Scheduling problem using Mixed Integer Quadratic Programming
Invited abstract in session FB-3: Approximation algorithms for scheduling problems, stream Approximation algorithms.
Friday, 10:15 - 11:45Room: C 104
Authors (first author is the speaker)
| 1. | Nóra Büki
|
| Department of Computational Optimization, University of Szeged | |
| 2. | János Balogh
|
| Department of Computational Optimization, University of Szeged | |
| 3. | József Békési
|
| Department of Computer Algorithms and Artificial Intelligence, Faculty of Science and Informatics, University of Szeged | |
| 4. | Gyorgy Dosa
|
| Mathematical Department, University of Pannonia | |
| 5. | Zsolt Tuza
|
| Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences |
Abstract
The Triangle Scheduling problem is a model for non-preemptive mixed criticality scheduling of unit length jobs. Two algorithms, Greedy and Bintree are both known to alpha-approximate the optimum value (with alpha = 1.5 and alpha = 2ln(2), respectively), but the tightness of those upper bounds is still an open question, with a best known gap as large as 0.45 for Greedy. We provide Mixed Integer Quadratic Programming formulations for both algorithms that, for certain small n, give an n-length input whose ALG makespan is the largest it can be for that input length. We are then able to use these small inputs to generate increasingly larger ones that provide better lower bounds, significantly reducing the gaps between the lower and upper bounds (LB=1.27 for Greedy and LB=1.35 for Bintree), and gaining insight about the different structures of inputs each algorithm performs badly on.
Keywords
- Mixed integer nonlinear optimization
Status: accepted
Back to the list of papers