default search action
Jirí Sgall
Jiri Sgall
Person information
- affiliation: Charles University in Prague, Computer Science Institute
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c63]Josef Minarík, Jirí Sgall:
Speed-Robust Scheduling Revisited. APPROX/RANDOM 2024: 8:1-8:20 - [c62]Martin Böhm, Matej Lieskovský, Sören Schmitt, Jirí Sgall, Rob van Stee:
Improved Online Load Balancing with Known Makespan. APPROX/RANDOM 2024: 10:1-10:21 - [c61]Jirí Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum, Zsolt Tuza:
No Tiling of the 70 × 70 Square with Consecutive Squares. FUN 2024: 28:1-28:16 - [i21]Martin Böhm, Matej Lieskovský, Sören Schmitt, Jirí Sgall, Rob van Stee:
Improved online load balancing with known makespan. CoRR abs/2407.08376 (2024) - [i20]Josef Minarík, Jirí Sgall:
Speed-robust scheduling revisited. CoRR abs/2407.11670 (2024) - 2023
- [j69]Jirí Sgall, Gerhard J. Woeginger:
Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms. Oper. Res. Lett. 51(6): 583-590 (2023) - [c60]Matej Lieskovský, Jirí Sgall, Andreas Emil Feldmann:
Approximation Algorithms and Lower Bounds for Graph Burning. APPROX/RANDOM 2023: 9:1-9:17 - [i19]Sunny Atalig, Marek Chrobak, Erfan Mousavian, Jiri Sgall, Pavel Veselý:
Structural Properties of Search Trees with 2-way Comparisons. CoRR abs/2311.02224 (2023) - 2022
- [j68]Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines. SIAM J. Comput. 51(5): 1626-1691 (2022) - [c59]Matej Lieskovský, Jirí Sgall:
Graph Burning and Non-uniform k-centers for Small Treewidth. WAOA 2022: 20-35 - 2021
- [j67]Martin Böhm, Lukasz Jez, Jirí Sgall, Pavel Veselý:
On packet scheduling with adversarial jamming and speedup. Ann. Oper. Res. 298(1): 7-42 (2021) - [j66]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý:
New results on multi-level aggregation. Theor. Comput. Sci. 861: 133-143 (2021) - [c58]Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý:
Improved Analysis of Online Balanced Clustering. WAOA 2021: 224-233 - [i18]Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý:
Improved Analysis of Online Balanced Clustering. CoRR abs/2107.00145 (2021) - 2020
- [j65]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý:
Online Algorithms for Multilevel Aggregation. Oper. Res. 68(1): 214-232 (2020)
2010 – 2019
- 2019
- [j64]János Balogh, József Békési, György Dósa, Jirí Sgall, Rob van Stee:
The optimal absolute ratio for online bin packing. J. Comput. Syst. Sci. 102: 1-17 (2019) - [j63]Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý:
Online packet scheduling with bounded delay and lookahead. Theor. Comput. Sci. 776: 95-113 (2019) - [c57]Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. SODA 2019: 123-142 - 2018
- [j62]Martin Böhm, György Dósa, Leah Epstein, Jirí Sgall, Pavel Veselý:
Colored Bin Packing: Online Algorithms and Lower Bounds. Algorithmica 80(1): 155-184 (2018) - [j61]Ernst Althaus, André Brinkmann, Peter Kling, Friedhelm Meyer auf der Heide, Lars Nagel, Sören Riechers, Jirí Sgall, Tim Süß:
Scheduling shared continuous resources on many-cores. J. Sched. 21(1): 77-92 (2018) - [j60]Marcin Bienkowski, Martin Böhm, Lukasz Jez, Pawel Laskos-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý:
Logarithmic price of buffer downscaling on line metrics. Theor. Comput. Sci. 707: 89-93 (2018) - [i17]Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A φ-Competitive Algorithm for Scheduling Packets with Deadlines. CoRR abs/1807.07177 (2018) - 2017
- [j59]Lukás Folwarczný, Jirí Sgall:
General Caching Is Hard: Even with Small Pages. Algorithmica 79(2): 319-339 (2017) - [j58]Martin Böhm, Jirí Sgall, Rob van Stee, Pavel Veselý:
A two-phase algorithm for bin stretching with stretching factor 1.5. J. Comb. Optim. 34(3): 810-828 (2017) - [j57]Martin Böhm, Jirí Sgall, Rob van Stee, Pavel Veselý:
Erratum to: A two-phase algorithm for bin stretching with stretching factor 1.5. J. Comb. Optim. 34(3): 829 (2017) - [j56]Martin Böhm, Jirí Sgall, Rob van Stee, Pavel Veselý:
Online bin stretching with three bins. J. Sched. 20(6): 601-621 (2017) - [c56]Martin Böhm, Lukasz Jez, Jirí Sgall, Pavel Veselý:
On Packet Scheduling with Adversarial Jamming and Speedup. WAOA 2017: 190-206 - [e5]Mohammad Reza Mousavi, Jirí Sgall:
Topics in Theoretical Computer Science - Second IFIP WG 1.8 International Conference, TTCS 2017, Tehran, Iran, September 12-14, 2017, Proceedings. Lecture Notes in Computer Science 10608, Springer 2017, ISBN 978-3-319-68952-4 [contents] - [i16]Martin Böhm, Lukasz Jez, Jirí Sgall, Pavel Veselý:
On Packet Scheduling with Adversarial Jamming and Speedup. CoRR abs/1705.07018 (2017) - 2016
- [j55]Leah Epstein, Lukasz Jez, Jirí Sgall, Rob van Stee:
Online Scheduling of Jobs with Fixed Start Times on Related Machines. Algorithmica 74(1): 156-176 (2016) - [j54]Marek Cygan, Lukasz Jez, Jirí Sgall:
Online Knapsack Revisited. Theory Comput. Syst. 58(1): 153-190 (2016) - [c55]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jiri Sgall, Kim Thang Nguyen, Pavel Veselý:
Online Algorithms for Multi-Level Aggregation. ESA 2016: 12:1-12:17 - [c54]Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý:
Online Packet Scheduling with Bounded Delay and Lookahead. ISAAC 2016: 21:1-21:13 - [r2]Jiri Sgall:
Online Preemptive Scheduling on Parallel Machines. Encyclopedia of Algorithms 2016: 1461-1464 - [i15]Martin Böhm, Jirí Sgall, Rob van Stee, Pavel Veselý:
The Best Two-Phase Algorithm for Bin Stretching. CoRR abs/1601.08111 (2016) - [i14]Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý:
Online Packet Scheduling with Bounded Delay and Lookahead. CoRR abs/1606.09395 (2016) - [i13]Marcin Bienkowski, Martin Böhm, Lukasz Jez, Pawel Laskos-Grabowski, Jan Marcinkowski, Jirí Sgall, Aleksandra Spyra, Pavel Veselý:
Logarithmic price of buffer downscaling on line metrics. CoRR abs/1610.04915 (2016) - 2015
- [j53]Krishnendu Chatterjee, Jirí Sgall:
Special Issue for the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, Klosterneuburg, Austria. Inf. Comput. 240: 1 (2015) - [j52]Tomás Ebenlendr, Jirí Sgall:
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption. Theory Comput. Syst. 56(1): 73-81 (2015) - [c53]Lukás Folwarczný, Jirí Sgall:
General Caching Is Hard: Even with Small Pages. ISAAC 2015: 116-126 - [c52]János Balogh, József Békési, György Dósa, Jirí Sgall, Rob van Stee:
The optimal absolute ratio for online bin packing. SODA 2015: 1425-1438 - [i12]Lukás Folwarczný, Jirí Sgall:
General Caching Is Hard: Even with Small Pages. CoRR abs/1506.07905 (2015) - [i11]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukás Folwarczný, Lukasz Jez, Jirí Sgall, Kim Thang Nguyen, Pavel Veselý:
Online Algorithms for Multi-Level Aggregation. CoRR abs/1507.02378 (2015) - 2014
- [j51]Tomás Ebenlendr, Marek Krcál, Jirí Sgall:
Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines. Algorithmica 68(1): 62-80 (2014) - [c51]Jirí Sgall:
Online Bin Packing: Old Algorithms and New Results. CiE 2014: 362-372 - [c50]György Dósa, Jirí Sgall:
Optimal Analysis of Best Fit Bin Packing. ICALP (1) 2014: 429-441 - [c49]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jirí Sgall:
Better Approximation Bounds for the Joint Replenishment Problem. SODA 2014: 42-54 - [c48]Martin Böhm, Jirí Sgall, Rob van Stee, Pavel Veselý:
Better Algorithms for Online Bin Stretching. WAOA 2014: 23-34 - [c47]Martin Böhm, Jirí Sgall, Pavel Veselý:
Online Colored Bin Packing. WAOA 2014: 35-46 - [c46]Jirí Sgall, Gerhard J. Woeginger:
Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms. WAOA 2014: 236-247 - [i10]Martin Böhm, Jirí Sgall, Pavel Veselý:
Online Colored Bin Packing. CoRR abs/1404.5548 (2014) - [i9]Martin Böhm, Jirí Sgall, Rob van Stee, Pavel Veselý:
Better Algorithms for Online Bin Stretching. CoRR abs/1404.5569 (2014) - 2013
- [j50]Luca Aceto, Monika Henzinger, Jirí Sgall:
38th International Colloquium on Automata, Languages and Programming. Inf. Comput. 222: 1 (2013) - [j49]Lukasz Jez, Jarett Schwartz, Jirí Sgall, József Békési:
Lower bounds for online makespan minimization on a small number of related machines. J. Sched. 16(5): 539-547 (2013) - [j48]Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better bounds for incremental frequency allocation in bipartite graphs. Theor. Comput. Sci. 514: 75-83 (2013) - [c45]György Dósa, Jirí Sgall:
First Fit bin packing: A tight analysis. STACS 2013: 538-549 - [c44]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall, Grzegorz Stachowiak:
Online Control Message Aggregation in Chain Networks. WADS 2013: 133-145 - [p1]Pavel Pudlák, Jirí Sgall:
An Upper Bound for a Communication Game Related to Time-Space Tradeoffs. The Mathematics of Paul Erdős I 2013: 399-407 - [e4]Krishnendu Chatterjee, Jirí Sgall:
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings. Lecture Notes in Computer Science 8087, Springer 2013, ISBN 978-3-642-40312-5 [contents] - [i8]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better Approximation Bounds for the Joint Replenishment Problem. CoRR abs/1307.2531 (2013) - 2012
- [c43]Leah Epstein, Lukasz Jez, Jirí Sgall, Rob van Stee:
Online Scheduling of Jobs with Fixed Start Times on Related Machines. APPROX-RANDOM 2012: 134-145 - [c42]Jirí Sgall:
Open Problems in Throughput Scheduling. ESA 2012: 2-11 - [c41]Jirí Sgall:
A New Analysis of Best Fit Bin Packing. FUN 2012: 315-321 - 2011
- [j47]Tomás Ebenlendr, Jirí Sgall:
Semi-Online Preemptive Scheduling: One Algorithm for All Variants. Theory Comput. Syst. 48(3): 577-613 (2011) - [c40]Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. ESA 2011: 251-262 - [c39]Marek Chrobak, Jirí Sgall, Gerhard J. Woeginger:
Two-Bounded-Space Bin Packing Revisited. ESA 2011: 263-274 - [c38]Tomás Ebenlendr, Jirí Sgall:
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption. WAOA 2011: 102-108 - [e3]Luca Aceto, Monika Henzinger, Jirí Sgall:
Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Lecture Notes in Computer Science 6755, Springer 2011, ISBN 978-3-642-22005-0 [contents] - [e2]Luca Aceto, Monika Henzinger, Jirí Sgall:
Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II. Lecture Notes in Computer Science 6756, Springer 2011, ISBN 978-3-642-22011-1 [contents] - [i7]Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. CoRR abs/1102.3393 (2011) - 2010
- [j46]Marek Chrobak, Jirí Sgall:
Three results on frequency assignment in linear cellular networks. Theor. Comput. Sci. 411(1): 131-137 (2010)
2000 – 2009
- 2009
- [j45]Tomás Ebenlendr, Wojciech Jawor, Jirí Sgall:
Preemptive Online Scheduling: Optimal Algorithms for All Speeds. Algorithmica 53(4): 504-522 (2009) - [j44]Marek Chrobak, Mathilde Hurand, Jirí Sgall:
Algorithms for testing fault-tolerance of sequenced jobs. J. Sched. 12(5): 501-515 (2009) - [j43]Tomás Ebenlendr, Jirí Sgall:
Optimal and online preemptive scheduling on uniformly related machines. J. Sched. 12(5): 517-527 (2009) - [j42]Jirí Sgall, Hadas Shachnai, Tami Tamir:
Periodic scheduling with obligatory vacations. Theor. Comput. Sci. 410(47-49): 5112-5121 (2009) - [c37]Marek Chrobak, Jirí Sgall:
Three Results on Frequency Assignment in Linear Cellular Networks. AAIM 2009: 129-139 - [c36]Ondrej Zajícek, Jirí Sgall, Tomás Ebenlendr:
Online Scheduling of Parallel Jobs on Hypercubes: Maximizing the Throughput. PPAM (2) 2009: 52-61 - [c35]Tomás Ebenlendr, Jirí Sgall:
Semi-Online Preemptive Scheduling: One Algorithm for All Variants. STACS 2009: 349-360 - 2008
- [j41]Daniel Král, Jirí Sgall, Tomás Tichý:
Randomized strategies for the plurality problem. Discret. Appl. Math. 156(17): 3305-3311 (2008) - [j40]Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman, Jirí Sgall:
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks. Theory Comput. 4(1): 1-20 (2008) - [c34]Tomás Ebenlendr, Marek Krcál, Jirí Sgall:
Graph balancing: a special case of scheduling unrelated parallel machines. SODA 2008: 483-490 - [c33]Tomás Ebenlendr, Jirí Sgall:
A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines. WAOA 2008: 43-52 - 2007
- [j39]Jirí Sgall, Gerhard J. Woeginger:
An Approximation Scheme For Cake Division With A Linear Number Of Cuts. Comb. 27(2): 205-211 (2007) - [j38]Gerhard J. Woeginger, Jirí Sgall:
On the complexity of cake cutting. Discret. Optim. 4(2): 213-220 (2007) - [j37]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. SIAM J. Comput. 36(6): 1709-1728 (2007) - [j36]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Improved online algorithms for buffer management in QoS switches. ACM Trans. Algorithms 3(4): 50 (2007) - [j35]Leah Epstein, Yanir Kleiman, Jirí Sgall, Rob van Stee:
Paging with connections: FIFO strikes again. Theor. Comput. Sci. 377(1-3): 55-64 (2007) - [c32]Jihuan Ding, Tomás Ebenlendr, Jirí Sgall, Guochuan Zhang:
Online Scheduling of Equal-Length Jobs on Parallel Machines. ESA 2007: 427-438 - [c31]Marek Chrobak, Mathilde Hurand, Jirí Sgall:
Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines. RTSS 2007: 139-148 - 2006
- [j34]Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms 4(2): 255-276 (2006) - [j33]Markus Bläser, Bodo Manthey, Jirí Sgall:
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algorithms 4(4): 623-632 (2006) - [c30]Tomás Ebenlendr, Wojciech Jawor, Jirí Sgall:
Preemptive Online Scheduling: Optimal Algorithms for All Speeds. ESA 2006: 327-339 - 2005
- [j32]Daniel Král, Jirí Sgall:
Coloring graphs from lists with bounded size of their union. J. Graph Theory 49(3): 177-186 (2005) - [j31]Jirí Síma, Jirí Sgall:
On the Nonlearnability of a Single Spiking Neuron. Neural Comput. 17(12): 2635-2647 (2005) - [j30]Marek Chrobak, Petr Kolman, Jirí Sgall:
The greedy algorithm for the minimum common string partition problem. ACM Trans. Algorithms 1(2): 350-366 (2005) - [c29]Jirí Sgall, Hadas Shachnai, Tami Tamir:
Fairness-Free Periodic Scheduling with Vacations. ESA 2005: 592-603 - [c28]Tomás Feder, Pavol Hell, Daniel Král, Jirí Sgall:
Two algorithms for general list matrix partitions. SODA 2005: 870-876 - [c27]Tomás Ebenlendr, John Noga, Jirí Sgall, Gerhard J. Woeginger:
A Note on Semi-online Machine Covering. WAOA 2005: 110-118 - [i6]Jirí Sgall:
Online Scheduling. Algorithms for Optimization with Incomplete Information 2005 - 2004
- [j29]Leah Epstein, Jirí Sgall:
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines. Algorithmica 39(1): 43-57 (2004) - [j28]Willem de Paepe, Jan Karel Lenstra, Jirí Sgall, René A. Sitters, Leen Stougie:
Computer-Aided Complexity Classification of Dial-a-Ride Problems. INFORMS J. Comput. 16(2): 120-132 (2004) - [j27]Eldar Fischer, Ilan Newman, Jirí Sgall:
Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms 24(2): 175-193 (2004) - [j26]Daniel Král, Vladan Majerech, Jirí Sgall, Tomás Tichý, Gerhard J. Woeginger:
It is tough to be a plumber. Theor. Comput. Sci. 313(3): 473-484 (2004) - [j25]Marek Chrobak, Jirí Sgall:
The weighted 2-server problem. Theor. Comput. Sci. 324(2-3): 289-312 (2004) - [c26]Marek Chrobak, Petr Kolman, Jirí Sgall:
The Greedy Algorithm for the Minimum Common String Partition Problem. APPROX-RANDOM 2004: 84-95 - [c25]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Improved Online Algorithms for Buffer Management in QoS Switches. ESA 2004: 204-215 - [c24]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. ICALP 2004: 358-370 - [c23]Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jirí Sgall, Tomás Tichý:
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. STACS 2004: 187-198 - [c22]Tomás Ebenlendr, Jirí Sgall:
Optimal and Online Preemptive Scheduling on Uniformly Related Machines. STACS 2004: 199-210 - [c21]Marek Chrobak, Jirí Sgall:
Errata to Analysis of the Harmonic Algorithm for Three Servers. STACS 2004: 656 - [r1]Kirk Pruhs, Jirí Sgall, Eric Torng:
Online Scheduling. Handbook of Scheduling 2004 - 2003
- [j24]Marek Chrobak, Leah Epstein, John Noga, Jirí Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania:
Preemptive scheduling in overloaded systems. J. Comput. Syst. Sci. 67(1): 183-197 (2003) - [c20]Jirí Sgall, Gerhard J. Woeginger:
A Lower Bound for Cake Cutting. ESA 2003: 459-469 - [c19]Marek Chrobak, Jirí Sgall:
Analysis of the Harmonic Algorithm for Three Servers. STACS 2003: 247-259 - 2002
- [j23]Eric Anderson, Marek Chrobak, John Noga, Jirí Sgall, Gerhard J. Woeginger:
Solution of a problem in DNA computing. Theor. Comput. Sci. 287(2): 387-391 (2002) - [j22]Yossi Azar, Oded Regev, Jirí Sgall, Gerhard J. Woeginger:
Off-line temporary tasks assignment. Theor. Comput. Sci. 287(