Jirí Sgall

According to our database1, Jirí Sgall authored at least 107 papers between 1990 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Online Algorithms for Multilevel Aggregation.
Oper. Res., 2020

2019
Online packet scheduling with bounded delay and lookahead.
Theor. Comput. Sci., 2019

The optimal absolute ratio for online bin packing.
J. Comput. Syst. Sci., 2019

A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Logarithmic price of buffer downscaling on line metrics.
Theor. Comput. Sci., 2018

Scheduling shared continuous resources on many-cores.
J. Sched., 2018

Colored Bin Packing: Online Algorithms and Lower Bounds.
Algorithmica, 2018

2017
Online bin stretching with three bins.
J. Sched., 2017

Erratum to: A two-phase algorithm for bin stretching with stretching factor 1.5.
J. Comb. Optim., 2017

A two-phase algorithm for bin stretching with stretching factor 1.5.
J. Comb. Optim., 2017

General Caching Is Hard: Even with Small Pages.
Algorithmica, 2017

On Packet Scheduling with Adversarial Jamming and Speedup.
Proceedings of the Approximation and Online Algorithms - 15th International Workshop, 2017

2016
Online Preemptive Scheduling on Parallel Machines.
Encyclopedia of Algorithms, 2016

Online Knapsack Revisited.
Theory Comput. Syst., 2016

The Best Two-Phase Algorithm for Bin Stretching.
CoRR, 2016

Online Scheduling of Jobs with Fixed Start Times on Related Machines.
Algorithmica, 2016

Online Algorithms for Multi-Level Aggregation.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption.
Theory Comput. Syst., 2015

Special Issue for the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, Klosterneuburg, Austria.
Inf. Comput., 2015

2014
Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines.
Algorithmica, 2014

Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Online Colored Bin Packing.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Better Algorithms for Online Bin Stretching.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Better Approximation Bounds for the Joint Replenishment Problem.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Optimal Analysis of Best Fit Bin Packing.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Online Bin Packing: Old Algorithms and New Results.
Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe, 2014

2013
Better bounds for incremental frequency allocation in bipartite graphs.
Theor. Comput. Sci., 2013

Lower bounds for online makespan minimization on a small number of related machines.
J. Sched., 2013

38th International Colloquium on Automata, Languages and Programming.
Inf. Comput., 2013

Better Approximation Bounds for the Joint Replenishment Problem.
CoRR, 2013

Online Control Message Aggregation in Chain Networks.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

First Fit bin packing: A tight analysis.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs.
Proceedings of the Mathematics of Paul Erdős I, 2013

2012
A New Analysis of Best Fit Bin Packing.
Proceedings of the Fun with Algorithms - 6th International Conference, 2012

Open Problems in Throughput Scheduling.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Semi-Online Preemptive Scheduling: One Algorithm for All Variants.
Theory Comput. Syst., 2011

Two-Bounded-Space Bin Packing Revisited.
Proceedings of the Algorithms - ESA 2011, 2011

2010
Three results on frequency assignment in linear cellular networks.
Theor. Comput. Sci., 2010

2009
Periodic scheduling with obligatory vacations.
Theor. Comput. Sci., 2009

Optimal and online preemptive scheduling on uniformly related machines.
J. Sched., 2009

Algorithms for testing fault-tolerance of sequenced jobs.
J. Sched., 2009

Preemptive Online Scheduling: Optimal Algorithms for All Speeds.
Algorithmica, 2009

Online Scheduling of Parallel Jobs on Hypercubes: Maximizing the Throughput.
Proceedings of the Parallel Processing and Applied Mathematics, 2009

2008
Single Source Multiroute Flows and Cuts on Uniform Capacity Networks.
Theory Comput., 2008

Randomized strategies for the plurality problem.
Discret. Appl. Math., 2008

A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

2007
Paging with connections: FIFO strikes again.
Theor. Comput. Sci., 2007

Improved online algorithms for buffer management in QoS switches.
ACM Trans. Algorithms, 2007

Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.
SIAM J. Comput., 2007

On the complexity of cake cutting.
Discret. Optim., 2007

An Approximation Scheme For Cake Division With A Linear Number Of Cuts.
Comb., 2007

Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines.
Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), 2007

Online Scheduling of Equal-Length Jobs on Parallel Machines.
Proceedings of the Algorithms, 2007

2006
Online competitive algorithms for maximizing weighted throughput of unit jobs.
J. Discrete Algorithms, 2006

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.
J. Discrete Algorithms, 2006

2005
The greedy algorithm for the minimum common string partition problem.
ACM Trans. Algorithms, 2005

On the Nonlearnability of a Single Spiking Neuron.
Neural Computation, 2005

Coloring graphs from lists with bounded size of their union.
Journal of Graph Theory, 2005

A Note on Semi-online Machine Covering.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Two algorithms for general list matrix partitions.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Fairness-Free Periodic Scheduling with Vacations.
Proceedings of the Algorithms, 2005

Online Scheduling.
Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

2004
Online Scheduling.
Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

It is tough to be a plumber.
Theor. Comput. Sci., 2004

The weighted 2-server problem.
Theor. Comput. Sci., 2004

Functions that have read-twice constant width branching programs are not necessarily testable.
Random Struct. Algorithms, 2004

Computer-Aided Complexity Classification of Dial-a-Ride Problems.
INFORMS J. Comput., 2004

Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines.
Algorithmica, 2004

Errata to Analysis of the Harmonic Algorithm for Three Servers.
Proceedings of the STACS 2004, 2004

Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.
Proceedings of the STACS 2004, 2004

2003
Preemptive scheduling in overloaded systems.
J. Comput. Syst. Sci., 2003

Analysis of the Harmonic Algorithm for Three Servers.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

A Lower Bound for Cake Cutting.
Proceedings of the Algorithms, 2003

2002
Off-line temporary tasks assignment.
Theor. Comput. Sci., 2002

Solution of a problem in DNA computing.
Theor. Comput. Sci., 2002

2001
Solution of David Gale's lion and man problem.
Theor. Comput. Sci., 2001

Communication complexity towards lower bounds on circuit depth.
Comput. Complex., 2001

Ancient and New Algorithms for Load Balancing in the <i>l</i><sub>p</sub> Norm.
Algorithmica, 2001

The complexity of coloring graphs without long induced paths.
Acta Cybern., 2001

The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000
DNF tautologies with a limited number of occurrences of every variable.
Theor. Comput. Sci., 2000

Multiprocessor Scheduling with Rejection.
SIAM J. Discret. Math., 2000

Efficient Dynamic Traitor Tracing.
SIAM J. Comput., 2000

Semi-online scheduling with decreasing job sizes.
Oper. Res. Lett., 2000

A lower bound for on-line scheduling on uniformly related machines.
Oper. Res. Lett., 2000

A simple analysis of the harmonic algorithm for two servers.
Inf. Process. Lett., 2000

1999
Bounds on Pairs of Families with Restricted Intersections.
Comb., 1999

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.
Comput. Complex., 1999

Randomized Online Scheduling on Two Uniform Machines.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
Optimal On-Line Scheduling of Parallel Jobs with Dependencies.
J. Comb. Optim., 1998

Ancient and New Algorithms for Load Balancing in the L<sub>p</sub> Norm.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997
Boolean Circuits, Tensor Ranks, and Communication Complexity.
SIAM J. Comput., 1997

A Lower Bound for Randomized On-Line Multiprocessor Scheduling.
Inf. Process. Lett., 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm
Electronic Colloquium on Computational Complexity (ECCC), 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Comput. Complex., 1997

1996
Solution of a covering problem related to labelled tournaments.
Journal of Graph Theory, 1996

Randomized On-Line Scheduling of Parallel Jobs.
J. Algorithms, 1996

On the Computational Power of DNA.
Discret. Appl. Math., 1996

Algebraic models of computation and interpolation for algebraic proof systems.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

Making DNA computers error resistant.
Proceedings of the DNA Based Computers, 1996

On-line Scheduling.
Proceedings of the Online Algorithms, 1996

1995
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs
Electronic Colloquium on Computational Complexity (ECCC), 1995

1994
Dynamic Scheduling on Parallel Machines.
Theor. Comput. Sci., 1994

On-Line Scheduling of Parallel Jobs.
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

1993
Optimal online scheduling of parallel jobs with dependencies.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1990
Interactive Computations of Optimal Solutions.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990


  Loading...