Jirí Sgall

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

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

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. Scheduling, 2018

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

2017
Online bin stretching with three bins.
J. Scheduling, 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

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

Online Packet Scheduling with Bounded Delay and Lookahead.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

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

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

The optimal absolute ratio for online bin packing.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

General Caching Is Hard: Even with Small Pages.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

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
Lower bounds for online makespan minimization on a small number of related machines.
J. Scheduling, 2013

38th International Colloquium on Automata, Languages and Programming.
Inf. Comput., 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

Online Scheduling of Jobs with Fixed Start Times on Related Machines.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption.
Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 2011

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

Better Bounds for Incremental Frequency Allocation in Bipartite Graphs.
Proceedings of the Algorithms - ESA 2011, 2011

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

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

Semi-Online Preemptive Scheduling: One Algorithm for All Variants.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

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

Three Results on Frequency Assignment in Linear Cellular Networks.
Proceedings of the Algorithmic Aspects in Information and Management, 2009

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

Randomized strategies for the plurality problem.
Discrete Applied Mathematics, 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

Graph balancing: a special case of scheduling unrelated parallel machines.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

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

On the complexity of cake cutting.
Discrete Optimization, 2007

An Approximation Scheme For Cake Division With A Linear Number Of Cuts.
Combinatorica, 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

Preemptive Online Scheduling: Optimal Algorithms for All Speeds.
Proceedings of the Algorithms, 2006

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

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 Journal on Computing, 2004

Optimal and Online Preemptive Scheduling on Uniformly Related Machines.
Proceedings of the STACS 2004, 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

Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Improved Online Algorithms for Buffer Management in QoS Switches.
Proceedings of the Algorithms, 2004

The Greedy Algorithm for the Minimum Common String Partition Problem.
Proceedings of the Approximation, 2004

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

Preemptive Scheduling in Overloaded Systems.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

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

Communication complexity towards lower bounds on circuit depth.
Computational Complexity, 2001

Ancient and New Algorithms for Load Balancing in the lp 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

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

The Weighted 2-Server Problem.
Proceedings of the STACS 2000, 2000

Efficient dynamic traitor tracing.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

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

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.
Computational Complexity, 1999

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

Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines.
Proceedings of the Algorithms, 1999

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

Bounds on Pairs of Families with Restricted Intersections
Electronic Colloquium on Computational Complexity (ECCC), 1998

Ancient and New Algorithms for Load Balancing in the Lp 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.
Computational Complexity, 1997

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

On the Computational Power of DNA.
Discrete Applied Mathematics, 1996

Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
Proceedings of the STACS 96, 1996

Multiprocessor Scheduling with Rejection.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Electronic Colloquium on Computational Complexity (ECCC), 1995

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

Randomized On-Line Scheduling of Parallel Jobs.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 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

1991
Dynamic Scheduling on Parallel Machines
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Communication Complexity Towards Lower Bounds on Circuit Depth
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

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


  Loading...