Jiri Sgall

Luca Aceto, Monika Henzinger, Jiri Sgall: 38th International Colloquium on Automata, Languages and Programming. Inf. Comput. 222: 1 (2013)

György Dósa, Jiri Sgall: First Fit bin packing: A tight analysis. STACS 2013: 538-549

Leah Epstein, Lukasz Jez, Jiri Sgall, Rob van Stee: Online Scheduling of Jobs with Fixed Start Times on Related Machines. APPROX-RANDOM 2012: 134-145

Jiri Sgall: Open Problems in Throughput Scheduling. ESA 2012: 2-11

Jiri Sgall: A New Analysis of Best Fit Bin Packing. FUN 2012: 315-321

Tomás Ebenlendr, Jiri Sgall: Semi-Online Preemptive Scheduling: One Algorithm for All Variants. Theory Comput. Syst. 48(3): 577-613 (2011)

Marek Chrobak, Lukasz Jez, Jiri Sgall: Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. ESA 2011: 251-262

Marek Chrobak, Jiri Sgall, Gerhard J. Woeginger: Two-Bounded-Space Bin Packing Revisited. ESA 2011: 263-274

Tomás Ebenlendr, Jiri Sgall: A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption. WAOA 2011: 102-108

Luca Aceto, Monika Henzinger, Jiri Sgall (Eds.): 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

Luca Aceto, Monika Henzinger, Jiri Sgall (Eds.): 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

Marek Chrobak, Lukasz Jez, Jiri Sgall: Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. CoRR abs/1102.3393 (2011)

Marek Chrobak, Jiri Sgall: Three results on frequency assignment in linear cellular networks. Theor. Comput. Sci. 411(1): 131-137 (2010)

Tomás Ebenlendr, Wojciech Jawor, Jiri Sgall: Preemptive Online Scheduling: Optimal Algorithms for All Speeds. Algorithmica 53(4): 504-522 (2009)

Marek Chrobak, Mathilde Hurand, Jiri Sgall: Algorithms for testing fault-tolerance of sequenced jobs. J. Scheduling 12(5): 501-515 (2009)

Tomás Ebenlendr, Jiri Sgall: Optimal and online preemptive scheduling on uniformly related machines. J. Scheduling 12(5): 517-527 (2009)

Jiri Sgall, Hadas Shachnai, Tami Tamir: Periodic scheduling with obligatory vacations. Theor. Comput. Sci. 410(47-49): 5112-5121 (2009)

Marek Chrobak, Jiri Sgall: Three Results on Frequency Assignment in Linear Cellular Networks. AAIM 2009: 129-139

Ondrej Zajícek, Jiri Sgall, Tomás Ebenlendr: Online Scheduling of Parallel Jobs on Hypercubes: Maximizing the Throughput. PPAM (2) 2009: 52-61

Tomás Ebenlendr, Jiri Sgall: Semi-Online Preemptive Scheduling: One Algorithm for All Variants. STACS 2009: 349-360

Daniel Král, Jiri Sgall, Tomás Tichý: Randomized strategies for the plurality problem. Discrete Applied Mathematics 156(17): 3305-3311 (2008)

Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman, Jiri Sgall: Single Source Multiroute Flows and Cuts on Uniform Capacity Networks. Theory of Computing 4(1): 1-20 (2008)

Tomás Ebenlendr, Marek Krcál, Jiri Sgall: Graph balancing: a special case of scheduling unrelated parallel machines. SODA 2008: 483-490

Tomás Ebenlendr, Jiri Sgall: A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines. WAOA 2008: 43-52

Jiri Sgall, Gerhard J. Woeginger: An Approximation Scheme For Cake Division With A Linear Number Of Cuts. Combinatorica 27(2): 205-211 (2007)

Gerhard J. Woeginger, Jiri Sgall: On the complexity of cake cutting. Discrete Optimization 4(2): 213-220 (2007)

Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý: Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. SIAM J. Comput. 36(6): 1709-1728 (2007)

Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý: Improved online algorithms for buffer management in QoS switches. ACM Transactions on Algorithms 3(4) (2007)

Leah Epstein, Yanir Kleiman, Jiri Sgall, Rob van Stee: Paging with connections: FIFO strikes again. Theor. Comput. Sci. 377(1-3): 55-64 (2007)

Jihuan Ding, Tomás Ebenlendr, Jiri Sgall, Guochuan Zhang: Online Scheduling of Equal-Length Jobs on Parallel Machines. ESA 2007: 427-438

Marek Chrobak, Mathilde Hurand, Jiri Sgall: Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines. RTSS 2007: 139-148

Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jiri Sgall, Tomás Tichý: Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms 4(2): 255-276 (2006)

Markus Bläser, Bodo Manthey, Jiri Sgall: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discrete Algorithms 4(4): 623-632 (2006)

Tomás Ebenlendr, Wojciech Jawor, Jiri Sgall: Preemptive Online Scheduling: Optimal Algorithms for All Speeds. ESA 2006: 327-339

Daniel Král, Jiri Sgall: Coloring graphs from lists with bounded size of their union. Journal of Graph Theory 49(3): 177-186 (2005)

Jirí Síma, Jiri Sgall: On the Nonlearnability of a Single Spiking Neuron. Neural Computation 17(12): 2635-2647 (2005)

Marek Chrobak, Petr Kolman, Jiri Sgall: The greedy algorithm for the minimum common string partition problem. ACM Transactions on Algorithms 1(2): 350-366 (2005)

Jiri Sgall: Online Scheduling. Algorithms for Optimization with Incomplete Information 2005

Jiri Sgall, Hadas Shachnai, Tami Tamir: Fairness-Free Periodic Scheduling with Vacations. ESA 2005: 592-603

Tomás Feder, Pavol Hell, Daniel Král, Jiri Sgall: Two algorithms for general list matrix partitions. SODA 2005: 870-876

Tomás Ebenlendr, John Noga, Jiri Sgall, Gerhard J. Woeginger: A Note on Semi-online Machine Covering. WAOA 2005: 110-118

Leah Epstein, Jiri Sgall: Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines. Algorithmica 39(1): 43-57 (2004)

Willem de Paepe, Jan Karel Lenstra, Jiri Sgall, René A. Sitters, Leen Stougie: Computer-Aided Complexity Classification of Dial-a-Ride Problems. INFORMS Journal on Computing 16(2): 120-132 (2004)

Eldar Fischer, Ilan Newman, Jiri Sgall: Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms 24(2): 175-193 (2004)

Daniel Král, Vladan Majerech, Jiri Sgall, Tomás Tichý, Gerhard J. Woeginger: It is tough to be a plumber. Theor. Comput. Sci. 303(3): 473-484 (2004)

Marek Chrobak, Jiri Sgall: The weighted 2-server problem. Theor. Comput. Sci. 324(2-3): 289-312 (2004)

Marek Chrobak, Petr Kolman, Jiri Sgall: The Greedy Algorithm for the Minimum Common String Partition Problem. APPROX-RANDOM 2004: 84-95

Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý: Improved Online Algorithms for Buffer Management in QoS Switches. ESA 2004: 204-215

Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý: Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. ICALP 2004: 358-370

Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jiri Sgall, Tomás Tichý: Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. STACS 2004: 187-198

Tomás Ebenlendr, Jiri Sgall: Optimal and Online Preemptive Scheduling on Uniformly Related Machines. STACS 2004: 199-210

Marek Chrobak, Jiri Sgall: Errata to Analysis of the Harmonic Algorithm for Three Servers. STACS 2004: 656

Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania: Preemptive scheduling in overloaded systems. J. Comput. Syst. Sci. 67(1): 183-197 (2003)

Jiri Sgall, Gerhard J. Woeginger: A Lower Bound for Cake Cutting. ESA 2003: 459-469

Marek Chrobak, Jiri Sgall: Analysis of the Harmonic Algorithm for Three Servers. STACS 2003: 247-259

Eric Anderson, Marek Chrobak, John Noga, Jiri Sgall, Gerhard J. Woeginger: Solution of a problem in DNA computing. Theor. Comput. Sci. 287(2): 387-391 (2002)

Yossi Azar, Oded Regev, Jiri Sgall, Gerhard J. Woeginger: Off-line temporary tasks assignment. Theor. Comput. Sci. 287(2): 419-428 (2002)

Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania: Preemptive Scheduling in Overloaded Systems. ICALP 2002: 800-811

Gerhard J. Woeginger, Jiri Sgall: The complexity of coloring graphs without long induced paths. Acta Cybern. 15(1): 107- (2001)

Adi Avidor, Yossi Azar, Jiri Sgall: Ancient and New Algorithms for Load Balancing in the l_p Norm. Algorithmica 29(3): 422-441 (2001)

Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiri Sgall: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3): 210-246 (2001)

Jiri Sgall: Solution of David Gale's lion and man problem. Theor. Comput. Sci. 259(1-2): 663-670 (2001)

Marek Chrobak, János Csirik, Csanád Imreh, John Noga, Jiri Sgall, Gerhard J. Woeginger: The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. ICALP 2001: 862-874

Jiri Sgall, Ales Pultr, Petr Kolman (Eds.): Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings. Lecture Notes in Computer Science 2136, Springer 2001, isbn 3-540-42496-2

Marek Chrobak, Jiri Sgall: A simple analysis of the harmonic algorithm for two servers. Inf. Process. Lett. 75(1-2): 75-77 (2000)

Leah Epstein, Jiri Sgall: A lower bound for on-line scheduling on uniformly related machines. Oper. Res. Lett. 26(1): 17-22 (2000)

Steven S. Seiden, Jiri Sgall, Gerhard J. Woeginger: Semi-online scheduling with decreasing job sizes. Oper. Res. Lett. 27(5): 215-221 (2000)

Omer Berkman, Michal Parnas, Jiri Sgall: Efficient Dynamic Traitor Tracing. SIAM J. Comput. 30(6): 1802-1828 (2000)

Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, Leen Stougie: Multiprocessor Scheduling with Rejection. SIAM J. Discrete Math. 13(1): 64-78 (2000)

Petr Savický, Jiri Sgall: DNF tautologies with a limited number of occurrences of every variable. Theor. Comput. Sci. 238(1-2): 495-498 (2000)

Omer Berkman, Michal Parnas, Jiri Sgall: Efficient dynamic traitor tracing. SODA 2000: 586-595

Marek Chrobak, Jiri Sgall: The Weighted 2-Server Problem. STACS 2000: 593-604

Russell Impagliazzo, Pavel Pudlák, Jiri Sgall: Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Computational Complexity 8(2): 127-144 (1999)

Jiri Sgall: Bounds on Pairs of Families with Restricted Intersections. Combinatorica 19(4): 555-566 (1999)

Leah Epstein, Jiri Sgall: Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines. ESA 1999: 151-162

Leah Epstein, John Noga, Steven S. Seiden, Jiri Sgall, Gerhard J. Woeginger: Randomized Online Scheduling on Two Uniform Machines. SODA 1999: 317-326

Carsten Damm, Stasys Jukna, Jiri Sgall: Some Bounds on Multiparty Communication Complexity of Pointer Jumping. Computational Complexity 7(2): 109-127 (1998)

Anja Feldmann, Ming-Yang Kao, Jiri Sgall, Shang-Hua Teng: Optimal On-Line Scheduling of Parallel Jobs with Dependencies. J. Comb. Optim. 1(4): 393-411 (1998)

Adi Avidor, Yossi Azar, Jiri Sgall: Ancient and New Algorithms for Load Balancing in the L_p Norm. SODA 1998: 426-435

Jiri Sgall: Bounds on Pairs of Families with Restricted Intersections. Electronic Colloquium on Computational Complexity (ECCC) 5(44) (1998)

Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Computational Complexity 6(3): 256-298 (1997)

Jiri Sgall: A Lower Bound for Randomized On-Line Multiprocessor Scheduling. Inf. Process. Lett. 63(1): 51-55 (1997)

Pavel Pudlák, Vojtech Rödl, Jiri Sgall: Boolean Circuits, Tensor Ranks, and Communication Complexity. SIAM J. Comput. 26(3): 605-633 (1997)

Russell Impagliazzo, Pavel Pudlák, Jiri Sgall: Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm. Electronic Colloquium on Computational Complexity (ECCC) 4(42) (1997)

Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall: On the Computational Power of DNA. Discrete Applied Mathematics 71(1-3): 79-94 (1996)

Jiri Sgall: Randomized On-Line Scheduling of Parallel Jobs. J. Algorithms 21(1): 149-175 (1996)

Jiri Sgall: Solution of a covering problem related to labelled tournaments. Journal of Graph Theory 23(2): 111-118 (1996)

Jiri Sgall: On-line Scheduling. Online Algorithms 1996: 196-231

Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, Jiri Sgall, Leen Stougie: Multiprocessor Scheduling with Rejection. SODA 1996: 95-103

Carsten Damm, Stasys Jukna, Jiri Sgall: Some Bounds on Multiparty Communication Complexity of Pointer Jumping. STACS 1996: 643-654

Jiri Sgall: Randomized On-Line Scheduling of Parallel Jobs. ISTCS 1995: 241-250

Pavel Pudlák, Jiri Sgall: An Upper Bound for a Communication Game Related to Time-Space Tradeoffs. Electronic Colloquium on Computational Complexity (ECCC) 2(10) (1995)

Carsten Damm, Stasys Jukna, Jiri Sgall: Some Bounds on Multiparty Communication Complexity of Pointer Jumping. Electronic Colloquium on Computational Complexity (ECCC) 2(44) (1995)

Carsten Damm, Stasys Jukna, Jiri Sgall: Some Bounds on Multiparty Communication Complexity of Pointer Jumping. Universität Trier, Mathematik/Informatik, Forschungsbericht 95-17 (1995)

Anja Feldmann, Jiri Sgall, Shang-Hua Teng: Dynamic Scheduling on Parallel Machines. Theor. Comput. Sci. 130(1): 49-72 (1994)

Jiri Sgall: On-Line Scheduling of Parallel Jobs. MFCS 1994: 159-176

Anja Feldmann, Ming-Yang Kao, Jiri Sgall, Shang-Hua Teng: Optimal online scheduling of parallel jobs with dependencies. STOC 1993: 642-651

Anja Feldmann, Jiri Sgall, Shang-Hua Teng: Dynamic Scheduling on Parallel Machines. FOCS 1991: 111-120

Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jiri Sgall: Communication Complexity Towards Lower Bounds on Circuit Depth. FOCS 1991: 249-257

Jan Krajícek, Pavel Pudlák, Jiri Sgall: Interactive Computations of Optimal Solutions. MFCS 1990: 48-60