%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Christoph Durr at 2017-06-21 22:41:25 +0200
%% Saved with string encoding Occidental (ASCII)
@article{LenstraTardos:90:Approximation-algorithms,
Author = {J. K. Lenstra, D. Shmoys and E. Tardos},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journaltitle = {Math. Progr.},
Title = {Approximation algorithms for scheduling unrelated parallel machines},
Volume = {46},
Year = {1990},
Annote = {$R||C_{\max}$ the approximation ratio is at least 3/2 unless P=NP\\
$R||C_{\max}$ has a polynomial time 2-approximation}}
@inbook{BillautCroce:17:When-Shop,
Author = {Jean-Charles Billaut and Federico Della Croce and Fabio Salassa and Vincent T'kindt},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {When Shop Scheduling Meets Dominoes, Eulerian and Hamiltonian Paths},
Year = {2017},
Annote = {$F2|no-idle;no-wait|C_{\max}$ can be solved in time $O(n)$\\
$F|no-idle;no-wait|C_{\max}$ can be solved in polynomial time by a reduction to Eulerian path in directed multi-graphs}}
@inproceedings{ImMoseley:17:Minimizing-Maximum,
Author = {Sungjin Im and Benjamin Moseley and Kirk Pruhs and Clifford Stein},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {Minimizing Maximum Flow Time on Related Machines via Immediate Dispatch and Dynamic Pricing},
Year = {2017},
Annote = {$Q|online-r_j|F_{\max}$ has competitive ratio at most 25/3 by a dynamic posted pricing algorithm}}
@inproceedings{BansalCloostermans:15:Minimizing-maximum,
Author = {Nikhil Bansal and Bouke Cloostermans},
Booktitle = {Approximation, Randomization, and Combinatorial Op- timization. Algorithms and Techniques (APPROX/RANDOM)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {85--95},
Title = {Minimizing maximum flow-time on related machines},
Year = {2015},
Annote = {$Q|online-r_j|F_{\max}$ has competitive ratio at most 13.5}}
@inproceedings{AnandBringmann:13:Minimizing-maximum,
Author = {S. Anand and Karl Bringmann and Tobias Friedrich and Naveen Garg and Amit Kumar},
Booktitle = {Automata, Languages, and Programming - 40th International Colloquium (ICALP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {13--24},
Title = {Minimizing maximum (weighted) flow-time on related and unrelated machines},
Year = {2013},
Annote = {$R|online-r_j|F_{\max}$ has a $(1+ \epsilon)$-speed $O(1/\epsilon)$-competitive algorithm\\
$R|online-r_j|F_{\max}$ without speed augmentation competitive ratio is $\Omega(m)$\\
$R|online-r_j|\max w_jF_j$ has a $(1+ \epsilon)$-speed $O(1/\epsilon^3)$-competitive algorithm\\
$R|online-r_j|\max w_jF_j$ any $O(1)$-speed algorithm has competitive ratio $\omega(1)$}}
@inproceedings{ImLi:17:Better-Unrelated,
Author = {Sungjin Im and Shi Li},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {Better Unrelated Machine Scheduling for Weighted Completion Time via Random sets from Non-Uniform Distributions},
Year = {2017},
Annote = {$R|r_j|\sum w_jC_j$ has a polynomial time approximation ratio $< 1.8786$ by LP-rounding\\
$R|r_j;pmtn|\sum w_jC_j$ has a polynomial time approximation ratio $< 1.99971$ by LP-rounding}}
@inproceedings{KnopKoutecky:17:Scheduling-Meets,
Author = {Dusan Knop and Martin Koutecky},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {Scheduling Meets n-fold Integer Programming},
Year = {2017},
Annote = {$Q||C_{\max}$ can be solved in time $\Theta^{O(\Theta^2)}n^{O(1)}$ for $\Theta=p_{\max}$\\
$R||C_{\max}$ can be solved in time $\Theta^{O(\Theta^2)}n^{O(1)}$ for $\Theta=p_{\max}^K$, where $K$ is the number of different kinds of machines\\
$R||\sum w_jC_j$ can be solved in time $\Theta^{O(\Theta^2)}n^{O(1)}$ for $\Theta=(\max\{p_{\max},w_\max\})^K$, where $K$ is the number of different kinds of machines}}
@inproceedings{BohmChrobak:17:Online-Packet,
Author = {Martin B{\"o}hm and Marek Chrobak and Lukasz Jez and Fei Li and Jiri Sgall and Pavel Vesely},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {Online Packet Scheduling with Bounded Delay and Lookahead},
Year = {2017},
Annote = {$1|online-r_j;p_j=1;d_j\leq r_j+4|\sum w_jU_j$ has competitive ratio $\Phi$, the golden ratio}}
@inproceedings{Hajek:01:On-the-competitiveness-of-on-line,
Author = {Bruce Hajek},
Booktitle = {Proc. Conference on Information Sciences and Systems},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {434---438},
Title = {On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time},
Year = {2001},
Annote = {$1|online-r_j;p_j=1|\sum w_jU_j$ scheduling always the heaviest job is 2-competitive\\
$1|online-r_j;p_j=1;d_j\leq r_j+2|\sum w_jU_j$ has competitive ratio at least $\Phi$, the golden ratio}}
@article{KesselmanLotker:04:Buffer-overflow,
Author = {Alexander Kesselman and Zvi Lotker and Yishay Mansour and Boaz Patt-Shamir and Baruch Schieber and Maxim Sviridenko},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journaltitle = {SIAM Journal on Computing},
Number = {3},
Pages = {563---583},
Title = {Buffer overflow management in QoS switches},
Volume = {33},
Year = {2004},
Annote = {$1|online-r_j;p_j=1|\sum w_jU_j$ scheduling always the heaviest job is 2-competitive\\
$1|online-r_j;p_j=1;d_j\leq r_j+2|\sum w_jU_j$ has competitive ratio $\Phi$, the golden ratio}}
@inproceedings{AndelmanMansour:03:Competitive-queueing,
Author = {Nir Andelman and Yishay Mansour and An Zhu},
Booktitle = {Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {761---770},
Title = {Competitive queueing policies for QoS switches},
Year = {2003},
Annote = {$1|online-r_j;p_j=1;d_j\leq r_j+2|\sum w_jU_j$ has competitive ratio at least $\Phi\approx1.618$, the golden ratio}}
@article{ChinFung:03:Online-scheduling,
Author = {Francis Y. L. Chin and Stanley P. Y. Fung},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journaltitle = {Algorithmica},
Number = {3},
Pages = {149---164},
Title = {Online scheduling with partial job values: Does timesharing or randomization help?},
Volume = {37},
Year = {2003},
Annote = {$1|online-r_j;p_j=1;d_j\leq r_j+2|\sum w_jU_j$ has competitive ratio at least $\Phi\approx1.618$, the golden ratio\\
$1|online-r_j;p_j=1;d_j\leq r_j+3|\sum w_jU_j$ has competitive ratio $\Phi\approx1.618$}}
@inproceedings{EnglertWestermann:07:Considering-suppressed,
Author = {Matthias Englert and Matthias Westermann},
Booktitle = {Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {209---218},
Title = {Considering suppressed packets improves buffer management in QoS switches},
Year = {2007},
Annote = {$1|online-r_j;p_j=1|\sum w_jU_j$ has competitive ratio at most $2\sqrt2-1\approx1.828$}}
@article{Jansen:10:An-EPTAS-for-scheduling,
Author = {Klaus Jansen},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journaltitle = {SIAM Journal on Discrete Mathematics},
Pages = {457--485},
Title = {An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables},
Volume = {24},
Year = {2010},
Annote = {$P||C_{\max}$ has an $(1+\epsilon)$-approximation in time $2^{O(1/\epsilon^2)log^3(1/\epsilon)} + O(n\log n)$}}
@inproceedings{ChenJansen:14:On-the-optimality-of-approximation,
Author = {L. Chen and K. Jansen and G. Zhang},
Booktitle = {25th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {657---668},
Title = {On the optimality of approximation schemes for the classical scheduling problem},
Year = {2014},
Annote = {$P||C_{\max}$ under the exponential time hypothesis (ETH) there is no $(1+\epsilon)$-approximation running in time $2^{(1/\epsilon)^{1-\delta}} +poly(n)$ for any $\delta>0$}}
@inproceedings{JansenKlein:16:Closing-the-gap-for-makespan,
Author = {K. Jansen and K. M. Klein and and J. Verschae},
Booktitle = {43rd International Colloquium on Automata, Languages, and Programming, (ICALP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {1--13},
Title = {Closing the gap for makespan scheduling via sparsification techniques},
Volume = {72},
Year = {2016},
Annote = {$Q||C_{\max}$ has an $(1+\epsilon)$-approximation in time $2^{O(1/\epsilon)log^4(1/\epsilon)} + O(n)$}}
@inproceedings{Schulz:96:Scheduling-to-minimize,
Author = {Andreas S. Schulz},
Booktitle = {Integer Programming and Combinatorial Optimization},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {301---315},
Title = {Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds},
Year = {1996},
Annote = {$1|prec|\sum w_jC_j$ has a polynomial time $2$-approximation, by solving a linear program (LP) and doing list scheduling in order of completion times in the LP solution\\
$1|r_j;prec|\sum w_jC_j$ has a polynomial time $3$-approximation, by solving a linear program (LP) and doing list scheduling in order of completion times in the LP solution\\}}
@inproceedings{BansalKhot:09:Optimal-long,
Author = {N. Bansal and S. Khot},
Booktitle = {Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Pages = {453---462},
Title = {Optimal long code test with one free bit},
Year = {2009},
Annote = {$1|prec|\sum w_jC_j$ has no polynomial time $(2-\epsilon)$-approximation under a stronger version of the unique game conjecture}}
@inproceedings{Skutella:17:A-2.542-Approximation-for-Precedence,
Author = {Martin Skutella},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time Objective},
Year = {2017},
Annote = {$1|r_j;prec|\sum w_jC_j$ has a polynomial time $\sqrt e/(\sqrt e-1)$-approximation}}
@article{MnichWiese:15:Scheduling-and-fixed-parameter,
Author = {Mnich, Matthias and Wiese, Andreas},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journal = {Mathematical Programming},
Number = {1-2},
Pages = {533--562},
Publisher = {Springer},
Title = {Scheduling and fixed-parameter tractability},
Volume = {154},
Year = {2015},
Annote = {$P||C_{\max}$ can be solved in time $f(p_{\max})\cdot n^{O(1)}$ for some function $f$}}
@article{BodlaenderFellows:95:W2-hardness-of-precedence,
Author = {Bodlaender, Hans L and Fellows, Michael R},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journal = {Operations Research Letters},
Number = {2},
Pages = {93--97},
Publisher = {Elsevier},
Title = {{W[2]}-hardness of precedence constrained k-processor scheduling},
Volume = {18},
Year = {1995},
Annote = {$P|prec;p_j=1|C_{\max}$ is W[2]-hard with respect to the number $m$ of machines}}
@inproceedings{BevernBredereck:16:Precedence-constrained-scheduling,
Author = {van Bevern, Ren{\'e} and Bredereck, Robert and Bulteau, Laurent and Komusiewicz, Christian and Talmon, Nimrod and Woeginger, Gerhard J},
Booktitle = {International Conference on Discrete Optimization and Operations Research},
Date-Modified = {2017-06-19 08:46:13 +0000},
Organization = {Springer},
Pages = {105--120},
Title = {Precedence-constrained scheduling problems parameterized by partial order width},
Year = {2016},
Annote = {$P2|prec;p_j\in\{1,2\}|C_{\max}$ is W[2]-hard with respect to the width of the partial order}}
@inproceedings{MkademMoukrim:17:An-Exact-Method,
Author = {Mohamed Amine Mkadem and Aziz Moukrim and Mehdi Serairi},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {An Exact Method for Solving the Two-Machine Flow-Shop Problem With Time Delays},
Year = {2017},
Annote = {$F2|t_j|C_{\max}$ can be solved by a branch-and-bound algorithm}}
@article{MoukrimRebaine:14:A-branch-and-bound,
Author = {A. Moukrim and D. Rebaine and M. Serairi.},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journaltitle = {RAIRO - Operations Research},
Number = {2},
Pages = {235--254},
Title = {A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays},
Volume = {48},
Year = {2014},
Annote = {$F2|p_{ij}=1;t_j|C_{\max}$ can be solved by a branch-and-bound algorithm}}
@inproceedings{MarinakisMarinaki:17:Hybrid-Adaptive,
Author = {Yannis Marinakis and Magdalene Marinaki},
Booktitle = {Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)},
Date-Modified = {2017-06-19 08:46:13 +0000},
Title = {Hybrid Adaptive Particle Swarm Optimization Algorithm for the Permutation Flowshop Scheduling Problem},
Year = {2017},
Annote = {$F||C_{\max}$ can be solved by a Hybrid Adaptive Particle Swarm Optimization algorithm}}
@article{Belouadah:92:Scheduling-with,
Author = {H. Belouadah, M. E. Posner, C. N. Potts},
Date-Modified = {2017-06-19 08:46:13 +0000},
Journaltitle = {Discrete Applied Mathematics},
Pages = {213--231},
Title = {Scheduling with release dates on a single machine to minimize total weighted completion time},
Volume = {36},
Year = {1992},
Annote = {$1|r_j|\sum w_jC_j$ can be solved by a branch-and-bound algorithm}}