Eberle, Franziska; Megow, Nicole; Schewior, Kevin Online throughput maximization on unrelated machines: commitment is no burden. (English) Zbl 07753161 ACM Trans. Algorithms 19, No. 1, Article No. 10, 25 p. (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{F. Eberle} et al., ACM Trans. Algorithms 19, No. 1, Article No. 10, 25 p. (2023; Zbl 07753161) Full Text: DOI arXiv
Moseley, Benjamin; Pruhs, Kirk; Stein, Clifford; Zhou, Rudy A competitive algorithm for throughput maximization on identical machines. (English) Zbl 1497.90096 Aardal, Karen (ed.) et al., Integer programming and combinatorial optimization. 23rd international conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13265, 402-414 (2022). MSC: 90B35 PDFBibTeX XMLCite \textit{B. Moseley} et al., Lect. Notes Comput. Sci. 13265, 402--414 (2022; Zbl 1497.90096) Full Text: DOI arXiv
Hyatt-Denesik, Dylan; Rahgoshay, Mirmahdi; Salavatipour, Mohammad R. Approximations for throughput maximization. (English) Zbl 07765369 Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 11, 17 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Hyatt-Denesik} et al., LIPIcs -- Leibniz Int. Proc. Inform. 181, Article 11, 17 p. (2020; Zbl 07765369) Full Text: DOI arXiv
Eberle, Franziska; Megow, Nicole; Schewior, Kevin Optimally handling commitment issues in online throughput maximization. (English) Zbl 07651180 Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 41, 15 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{F. Eberle} et al., LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 41, 15 p. (2020; Zbl 07651180) Full Text: DOI
Chen, Lin; Eberle, Franziska; Megow, Nicole; Schewior, Kevin; Stein, Cliff A general framework for handling commitment in online throughput maximization. (English) Zbl 1446.90075 Math. Program. 183, No. 1-2 (B), 215-247 (2020). MSC: 90B35 68M20 PDFBibTeX XMLCite \textit{L. Chen} et al., Math. Program. 183, No. 1--2 (B), 215--247 (2020; Zbl 1446.90075) Full Text: DOI
Yu, Ge; Jacobson, Sheldon H. Online C-benevolent job scheduling on multiple machines. (English) Zbl 1403.90377 Optim. Lett. 12, No. 2, 251-263 (2018). MSC: 90B35 90C59 PDFBibTeX XMLCite \textit{G. Yu} and \textit{S. H. Jacobson}, Optim. Lett. 12, No. 2, 251--263 (2018; Zbl 1403.90377) Full Text: DOI
Epstein, Leah; Levin, Asaf; Segev, Danny; Weimann, Oren Improved bounds for randomized preemptive online matching. (English) Zbl 1388.68314 Inf. Comput. 259, Part 1, 31-40 (2018). MSC: 68W27 68R10 68W20 PDFBibTeX XMLCite \textit{L. Epstein} et al., Inf. Comput. 259, Part 1, 31--40 (2018; Zbl 1388.68314) Full Text: DOI
Chatterjee, Krishnendu; Pavlogiannis, Andreas; Kößler, Alexander; Schmid, Ulrich Automated competitive analysis of real-time scheduling with graph games. (English) Zbl 1425.68044 Real-Time Syst. 54, No. 1, 166-207 (2018). MSC: 68M20 68Q17 90B35 91A43 PDFBibTeX XMLCite \textit{K. Chatterjee} et al., Real-Time Syst. 54, No. 1, 166--207 (2018; Zbl 1425.68044) Full Text: DOI
Jeż, Łukasz; Mansour, Yishay; Patt-Shamir, Boaz Scheduling multipacket frames with frame deadlines. (English) Zbl 1386.90058 J. Sched. 20, No. 6, 623-634 (2017). MSC: 90B35 68M20 PDFBibTeX XMLCite \textit{Ł. Jeż} et al., J. Sched. 20, No. 6, 623--634 (2017; Zbl 1386.90058) Full Text: DOI Link
Epstein, Leah; Jeż, Łukasz; Sgall, Jiří; van Stee, Rob Online scheduling of jobs with fixed start times on related machines. (English) Zbl 1333.90040 Algorithmica 74, No. 1, 156-176 (2016). MSC: 90B35 68W27 PDFBibTeX XMLCite \textit{L. Epstein} et al., Algorithmica 74, No. 1, 156--176 (2016; Zbl 1333.90040) Full Text: DOI
Fung, Stanley P. Y.; Poon, Chung Keung; Zheng, Feifeng Improved randomized online scheduling of intervals and jobs. (English) Zbl 1319.68257 Theory Comput. Syst. 55, No. 1, 202-228 (2014). MSC: 68W27 68W20 90B35 PDFBibTeX XMLCite \textit{S. P. Y. Fung} et al., Theory Comput. Syst. 55, No. 1, 202--228 (2014; Zbl 1319.68257) Full Text: DOI arXiv
Fung, Stanley P. Y. Online scheduling with preemption or non-completion penalties. (English) Zbl 1297.90042 J. Sched. 17, No. 2, 173-183 (2014). MSC: 90B35 68W27 PDFBibTeX XMLCite \textit{S. P. Y. Fung}, J. Sched. 17, No. 2, 173--183 (2014; Zbl 1297.90042) Full Text: DOI
Naor, Joseph (Seffi); Rosén, Adi; Scalosub, Gabriel Online time-constrained scheduling in linear and ring networks. (English) Zbl 1203.90070 J. Discrete Algorithms 8, No. 4, 346-355 (2010). MSC: 90B35 PDFBibTeX XMLCite \textit{J. Naor} et al., J. Discrete Algorithms 8, No. 4, 346--355 (2010; Zbl 1203.90070) Full Text: DOI
Devadas, Vinay; Li, Fei; Aydin, Hakan Competitive analysis of online real-time scheduling algorithms under hard energy constraint. (English) Zbl 1204.68037 Real-Time Syst. 46, No. 1, 88-120 (2010). MSC: 68M20 68W27 PDFBibTeX XMLCite \textit{V. Devadas} et al., Real-Time Syst. 46, No. 1, 88--120 (2010; Zbl 1204.68037) Full Text: DOI
Banerjee, Satyajit On the lower bound of the competitive ratio for the weighted online roommates problem. (English) Zbl 1200.68287 Discrete Math. Algorithms Appl. 2, No. 2, 257-262 (2010). MSC: 68W27 05C70 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{S. Banerjee}, Discrete Math. Algorithms Appl. 2, No. 2, 257--262 (2010; Zbl 1200.68287) Full Text: DOI
Epstein, Leah; Erlebach, Thomas; Levin, Asaf Variable sized online interval coloring with bandwidth. (English) Zbl 1172.68059 Algorithmica 53, No. 3, 385-401 (2009). MSC: 68W05 05C15 05C78 05C85 68Q17 68W25 68W40 PDFBibTeX XMLCite \textit{L. Epstein} et al., Algorithmica 53, No. 3, 385--401 (2009; Zbl 1172.68059) Full Text: DOI Link
Fung, Stanley P. Y.; Poon, Chung Keung; Zheng, Feifeng Improved randomized online scheduling of unit length intervals and jobs. (English) Zbl 1209.68660 Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 6th international workshop, WAOA 2008, Karlsruhe, Germany, September 18–19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-93979-5/pbk). Lecture Notes in Computer Science 5426, 53-66 (2009). MSC: 68W27 68W20 90B35 PDFBibTeX XMLCite \textit{S. P. Y. Fung} et al., Lect. Notes Comput. Sci. 5426, 53--66 (2009; Zbl 1209.68660) Full Text: DOI
Fung, Stanley P. Y. Lower bounds on online deadline scheduling with preemption penalties. (English) Zbl 1191.68098 Inf. Process. Lett. 108, No. 4, 214-218 (2008). MSC: 68M20 PDFBibTeX XMLCite \textit{S. P. Y. Fung}, Inf. Process. Lett. 108, No. 4, 214--218 (2008; Zbl 1191.68098) Full Text: DOI
Fung, Stanley P. Y.; Poon, Chung Keung; Zheng, Feifeng Online interval scheduling: Randomized and multiprocessor cases. (English) Zbl 1176.68038 J. Comb. Optim. 16, No. 3, 248-262 (2008). MSC: 68M20 90B35 PDFBibTeX XMLCite \textit{S. P. Y. Fung} et al., J. Comb. Optim. 16, No. 3, 248--262 (2008; Zbl 1176.68038) Full Text: DOI Link
Fung, Stanley P. Y.; Chin, Francis Y. L.; Shen, Hong Online scheduling of unit jobs with bounded importance ratio. (English) Zbl 1097.68021 Int. J. Found. Comput. Sci. 16, No. 3, 581-598 (2005). MSC: 68M20 90B35 PDFBibTeX XMLCite \textit{S. P. Y. Fung} et al., Int. J. Found. Comput. Sci. 16, No. 3, 581--598 (2005; Zbl 1097.68021) Full Text: DOI
Chin, Francis Y. L.; Fung, Stanley P. Y. Improved competitive algorithms for online scheduling with partial job values. (English) Zbl 1071.68013 Theor. Comput. Sci. 325, No. 3, 467-478 (2004). MSC: 68M20 PDFBibTeX XMLCite \textit{F. Y. L. Chin} and \textit{S. P. Y. Fung}, Theor. Comput. Sci. 325, No. 3, 467--478 (2004; Zbl 1071.68013) Full Text: DOI
Palis, Michael A. On the competitiveness of online real-time scheduling with rate of progress guarantees. (English) Zbl 1101.68423 Int. J. Found. Comput. Sci. 14, No. 3, 359-370 (2003). MSC: 68M20 PDFBibTeX XMLCite \textit{M. A. Palis}, Int. J. Found. Comput. Sci. 14, No. 3, 359--370 (2003; Zbl 1101.68423) Full Text: DOI
Chin, Francis Y. L.; Fung, Stanley P. Y. Online scheduling with partial job values: does timesharing or randomization help? (English) Zbl 1087.68519 Algorithmica 37, No. 3, 149-164 (2003). MSC: 68M20 PDFBibTeX XMLCite \textit{F. Y. L. Chin} and \textit{S. P. Y. Fung}, Algorithmica 37, No. 3, 149--164 (2003; Zbl 1087.68519) Full Text: DOI Link
Chrobak, Marek; Epstein, Leah; Noga, John; Sgall, Jiří; van Stee, Rob; Tichý, Tomáš; Vakhania, Nodari Preemptive scheduling in overloaded systems. (English) Zbl 1054.68015 J. Comput. Syst. Sci. 67, No. 1, 183-197 (2003). MSC: 68M20 PDFBibTeX XMLCite \textit{M. Chrobak} et al., J. Comput. Syst. Sci. 67, No. 1, 183--197 (2003; Zbl 1054.68015) Full Text: DOI
Koo, Chiu-Yuen; Lam, Tak-Wah; Ngan, Tsuen-Wan; Sadakane, Kunihiko; To, Kar-Keung On-line scheduling with tight deadlines. (English) Zbl 1053.68015 Theor. Comput. Sci. 295, No. 1-3, 251-261 (2003). MSC: 68M20 PDFBibTeX XMLCite \textit{C.-Y. Koo} et al., Theor. Comput. Sci. 295, No. 1--3, 251--261 (2003; Zbl 1053.68015) Full Text: DOI
Garofalakis, Minos; Ioannidis, Yannis; Özden, Banu; Silberschatz, Avi Competitive on-line scheduling of continuous-media streams. (English) Zbl 1013.68046 J. Comput. Syst. Sci. 64, No. 2, 219-248 (2002). MSC: 68M20 68M10 PDFBibTeX XMLCite \textit{M. Garofalakis} et al., J. Comput. Syst. Sci. 64, No. 2, 219--248 (2002; Zbl 1013.68046) Full Text: DOI
Dasgupta, Bhaskar; Palis, Michael A. Online real-time preemptive scheduling of jobs with deadlines on multiple machines. (English) Zbl 0995.90029 J. Sched. 4, No. 6, 297-312 (2001). MSC: 90B35 90C59 PDFBibTeX XMLCite \textit{B. Dasgupta} and \textit{M. A. Palis}, J. Sched. 4, No. 6, 297--312 (2001; Zbl 0995.90029) Full Text: DOI
Kwon, Oh-Heum; Chwa, Kyung-Yong Scheduling parallel tasks with individual deadlines. (English) Zbl 0913.68014 Theor. Comput. Sci. 215, No. 1-2, 209-223 (1999). MSC: 68M20 68W15 PDFBibTeX XMLCite \textit{O.-H. Kwon} and \textit{K.-Y. Chwa}, Theor. Comput. Sci. 215, No. 1--2, 209--223 (1999; Zbl 0913.68014) Full Text: DOI
Teik, Guan Tan; Wynne, Hsu Approximating scheduling for multimedia applications under overload conditions. (English) Zbl 1044.90512 Int. J. Approx. Reasoning 19, No. 1-2, 57-71 (1998). MSC: 90B35 68W25 PDFBibTeX XMLCite \textit{G. T. Teik} and \textit{H. Wynne}, Int. J. Approx. Reasoning 19, No. 1--2, 57--71 (1998; Zbl 1044.90512) Full Text: DOI
Seiden, Steven S. Randomized online interval scheduling. (English) Zbl 0914.90168 Oper. Res. Lett. 22, No. 4-5, 171-177 (1998). MSC: 90B35 PDFBibTeX XMLCite \textit{S. S. Seiden}, Oper. Res. Lett. 22, No. 4--5, 171--177 (1998; Zbl 0914.90168) Full Text: DOI
Yang, Qifan A 2.79 competitive on-line algorithm for two processor real-time systems with uniform value density. (English) Zbl 0878.90070 Appl. Math., Ser. B (Engl. Ed.) 12, No. 3, 333-342 (1997). MSC: 90B50 PDFBibTeX XMLCite \textit{Q. Yang}, Appl. Math., Ser. B (Engl. Ed.) 12, No. 3, 333--342 (1997; Zbl 0878.90070) Full Text: DOI
Schmid, U. Random trees in queueing systems with deadlines. (English) Zbl 0874.68017 Theor. Comput. Sci. 144, No. 1-2, 277-314 (1995). MSC: 68M20 PDFBibTeX XMLCite \textit{U. Schmid}, Theor. Comput. Sci. 144, No. 1--2, 277--314 (1995; Zbl 0874.68017) Full Text: DOI
Kwon, Oh-Heum; Chwa, Kyung-Yong Scheduling parallel tasks with individual deadlines. (English) Zbl 1512.90099 Staples, John (ed.) et al., Algorithms and computations. 6th international symposium, ISAAC ’95, Cairns, Australia, December 4–6, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 1004, 198-207 (1995). MSC: 90B35 68W25 PDFBibTeX XMLCite \textit{O.-H. Kwon} and \textit{K.-Y. Chwa}, Lect. Notes Comput. Sci. 1004, 198--207 (1995; Zbl 1512.90099) Full Text: DOI
Koren, Gilad; Shasha, Dennis MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling. (English) Zbl 0938.68549 Theor. Comput. Sci. 128, No. 1-2, 75-97 (1994). MSC: 68M20 PDFBibTeX XMLCite \textit{G. Koren} and \textit{D. Shasha}, Theor. Comput. Sci. 128, No. 1--2, 75--97 (1994; Zbl 0938.68549) Full Text: DOI