Jirí Sgall

Proceedings of the Approximation, 2024

Improved Online Load Balancing with Known Makespan.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms.

[BibT_eX]

[DOI]

Oper. Res. Lett., November, 2023

Structural Properties of Search Trees with 2-way Comparisons.

[BibT_eX]

[DOI]

CoRR, 2023

Approximation Algorithms and Lower Bounds for Graph Burning.

[BibT_eX]

[DOI]

Matej Lieskovský

Andreas Emil Feldmann

Proceedings of the Approximation, 2023

2022

A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Graph Burning and Non-uniform k-centers for Small Treewidth.

[BibT_eX]

[DOI]

Matej Lieskovský

Friedhelm Meyer auf der Heide

Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

2021

New results on multi-level aggregation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

On packet scheduling with adversarial jamming and speedup.

[BibT_eX]

[DOI]

Ann. Oper. Res., 2021

Improved Analysis of Online Balanced Clustering.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 19th International Workshop, 2021

2020

Online Algorithms for Multilevel Aggregation.

[BibT_eX]

[DOI]

Oper. Res., 2020

2019

Online packet scheduling with bounded delay and lookahead.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

The optimal absolute ratio for online bin packing.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2019

A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Logarithmic price of buffer downscaling on line metrics.

[BibT_eX]

[DOI]

Marcin Bienkowski

Martin Böhm

Lukasz Jez

Pawel Laskos-Grabowski

Theor. Comput. Sci., 2018

Scheduling shared continuous resources on many-cores.

[BibT_eX]

[DOI]

Ernst Althaus

André Brinkmann

Peter Kling

J. Sched., 2018

Colored Bin Packing: Online Algorithms and Lower Bounds.

[BibT_eX]

[DOI]

Algorithmica, 2018

2017

Online bin stretching with three bins.

[BibT_eX]

[DOI]

J. Sched., 2017

Erratum to: A two-phase algorithm for bin stretching with stretching factor 1.5.

[BibT_eX]

[DOI]

J. Comb. Optim., 2017

A two-phase algorithm for bin stretching with stretching factor 1.5.

[BibT_eX]

[DOI]

J. Comb. Optim., 2017

General Caching Is Hard: Even with Small Pages.

[BibT_eX]

[DOI]

Lukás Folwarczný

Algorithmica, 2017

2016

Online Preemptive Scheduling on Parallel Machines.

[BibT_eX]

[DOI]

Jiri Sgall

Encyclopedia of Algorithms, 2016

Online Knapsack Revisited.

[BibT_eX]

[DOI]

Marek Cygan

Lukasz Jez

Theory Comput. Syst., 2016

The Best Two-Phase Algorithm for Bin Stretching.

[BibT_eX]

[DOI]

CoRR, 2016

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

[BibT_eX]

[DOI]

Algorithmica, 2016

Online Algorithms for Multi-Level Aggregation.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

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

[BibT_eX]

[DOI]

Krishnendu Chatterjee

Inf. Comput., 2015

2014

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

[BibT_eX]

[DOI]

Marek Krcál

Algorithmica, 2014

Online Colored Bin Packing.

[BibT_eX]

[DOI]

Martin Böhm

Pavel Veselý

Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Better Algorithms for Online Bin Stretching.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

Better Approximation Bounds for the Joint Replenishment Problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Optimal Analysis of Best Fit Bin Packing.

[BibT_eX]

[DOI]

György Dósa

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Online Bin Packing: Old Algorithms and New Results.

[BibT_eX]

[DOI]

Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe, 2014

2013

Better bounds for incremental frequency allocation in bipartite graphs.

[BibT_eX]

[DOI]

Lukasz Jez

Theor. Comput. Sci., 2013

Lower bounds for online makespan minimization on a small number of related machines.

[BibT_eX]

[DOI]

J. Sched., 2013

38th International Colloquium on Automata, Languages and Programming.

[BibT_eX]

[DOI]

Luca Aceto

Monika Henzinger

Inf. Comput., 2013

Better Approximation Bounds for the Joint Replenishment Problem.

[BibT_eX]

[DOI]

CoRR, 2013

Online Control Message Aggregation in Chain Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

First Fit bin packing: A tight analysis.

[BibT_eX]

[DOI]

György Dósa

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.

[BibT_eX]

[DOI]

Proceedings of the Mathematics of Paul Erdős I, 2013

2012

A New Analysis of Best Fit Bin Packing.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

Open Problems in Throughput Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

Semi-Online Preemptive Scheduling: One Algorithm for All Variants.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Two-Bounded-Space Bin Packing Revisited.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

Three results on frequency assignment in linear cellular networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

2009

Periodic scheduling with obligatory vacations.

[BibT_eX]

[DOI]

Hadas Shachnai

Tami Tamir

Theor. Comput. Sci., 2009

Optimal and online preemptive scheduling on uniformly related machines.

[BibT_eX]

[DOI]

J. Sched., 2009

Algorithms for testing fault-tolerance of sequenced jobs.

[BibT_eX]

[DOI]

Mathilde Hurand

J. Sched., 2009

Preemptive Online Scheduling: Optimal Algorithms for All Speeds.

[BibT_eX]

[DOI]

Wojciech Jawor

Algorithmica, 2009

Online Scheduling of Parallel Jobs on Hypercubes: Maximizing the Throughput.

[BibT_eX]

[DOI]

Ondrej Zajícek

Proceedings of the Parallel Processing and Applied Mathematics, 2009

2008

Single Source Multiroute Flows and Cuts on Uniform Capacity Networks.

[BibT_eX]

[DOI]

Theory Comput., 2008

Randomized strategies for the plurality problem.

[BibT_eX]

[DOI]

Daniel Král

Tomás Tichý

Discret. Appl. Math., 2008

A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

2007

Paging with connections: FIFO strikes again.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Improved online algorithms for buffer management in QoS switches.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

On the complexity of cake cutting.

[BibT_eX]

[DOI]

Discret. Optim., 2007

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

[BibT_eX]

[DOI]

Comb., 2007

Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines.

[BibT_eX]

[DOI]

Mathilde Hurand

Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), 2007

Online Scheduling of Equal-Length Jobs on Parallel Machines.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2007

2006

Online competitive algorithms for maximizing weighted throughput of unit jobs.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2006

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.

[BibT_eX]

[DOI]

Markus Bläser

Bodo Manthey

J. Discrete Algorithms, 2006

2005

The greedy algorithm for the minimum common string partition problem.

[BibT_eX]

[DOI]

Petr Kolman

ACM Trans. Algorithms, 2005

On the Nonlearnability of a Single Spiking Neuron.

[BibT_eX]

[DOI]

Jirí Síma

Neural Comput., 2005

Coloring graphs from lists with bounded size of their union.

[BibT_eX]

[DOI]

Daniel Král

J. Graph Theory, 2005

A Note on Semi-online Machine Covering.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Two algorithms for general list matrix partitions.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Fairness-Free Periodic Scheduling with Vacations.

[BibT_eX]

[DOI]

Hadas Shachnai

Tami Tamir

Proceedings of the Algorithms, 2005

Online Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

2004

Online Scheduling.

[BibT_eX]

[DOI]

Kirk Pruhs

Eric Torng

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

It is tough to be a plumber.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

The weighted 2-server problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Functions that have read-twice constant width branching programs are not necessarily testable.

[BibT_eX]

[DOI]

Eldar Fischer

Ilan Newman

Random Struct. Algorithms, 2004

Computer-Aided Complexity Classification of Dial-a-Ride Problems.

[BibT_eX]

[DOI]

INFORMS J. Comput., 2004

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

[BibT_eX]

[DOI]

Leah Epstein

Algorithmica, 2004

Errata to Analysis of the Harmonic Algorithm for Three Servers.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

2003

Preemptive scheduling in overloaded systems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Analysis of the Harmonic Algorithm for Three Servers.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

2002

Off-line temporary tasks assignment.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Solution of a problem in DNA computing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

2001

Solution of David Gale's lion and man problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Communication complexity towards lower bounds on circuit depth.

[BibT_eX]

[DOI]

Comput. Complex., 2001

Ancient and New Algorithms for Load Balancing in the lp Norm.

[BibT_eX]

[DOI]

Adi Avidor

Yossi Azar

Algorithmica, 2001

The complexity of coloring graphs without long induced paths.

[BibT_eX]

[DOI]

Acta Cybern., 2001

The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000

DNF tautologies with a limited number of occurrences of every variable.

[BibT_eX]

[DOI]

Petr Savický

Alberto Marchetti-Spaccamela

Theor. Comput. Sci., 2000

Multiprocessor Scheduling with Rejection.

[BibT_eX]

[DOI]

Yair Bartal

Stefano Leonardi

Leen Stougie

SIAM J. Discret. Math., 2000

Efficient Dynamic Traitor Tracing.

[BibT_eX]

[DOI]

Omer Berkman

Michal Parnas

SIAM J. Comput., 2000

Semi-online scheduling with decreasing job sizes.

[BibT_eX]

[DOI]

Steven S. Seiden

Oper. Res. Lett., 2000

A lower bound for on-line scheduling on uniformly related machines.

[BibT_eX]

[DOI]

Leah Epstein

Oper. Res. Lett., 2000

A simple analysis of the harmonic algorithm for two servers.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

1999

Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm.

[BibT_eX]

[DOI]

Russell Impagliazzo

Comput. Complex., 1999

Randomized Online Scheduling on Two Uniform Machines.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Optimal On-Line Scheduling of Parallel Jobs with Dependencies.

[BibT_eX]

[DOI]

J. Comb. Optim., 1998

Bounds on Pairs of Families with Restricted Intersections

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Some Bounds on Multiparty Communication Complexity of Pointer Jumping.

[BibT_eX]

[DOI]

Carsten Damm

Stasys Jukna

Comput. Complex., 1998

Ancient and New Algorithms for Load Balancing in the Lp Norm.

[BibT_eX]

[DOI]

Adi Avidor

Yossi Azar

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997

Boolean Circuits, Tensor Ranks, and Communication Complexity.

[BibT_eX]

[DOI]

Vojtech Rödl

SIAM J. Comput., 1997

A Lower Bound for Randomized On-Line Multiprocessor Scheduling.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

[BibT_eX]

[DOI]

Russell Impagliazzo

Electron. Colloquium Comput. Complex., 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.

[BibT_eX]

[DOI]

Alexander A. Razborov

Comput. Complex., 1997

1996

Solution of a covering problem related to labelled tournaments.

[BibT_eX]

[DOI]

J. Graph Theory, 1996

Randomized On-Line Scheduling of Parallel Jobs.

[BibT_eX]

[DOI]

J. Algorithms, 1996

On the Computational Power of DNA.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1996

Algebraic models of computation and interpolation for algebraic proof systems.

[BibT_eX]

[DOI]

Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

Making DNA computers error resistant.

[BibT_eX]

[DOI]

Proceedings of the DNA Based Computers, 1996

On-line Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Online Algorithms, 1996

1995

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

1994

Dynamic Scheduling on Parallel Machines.

[BibT_eX]

[DOI]

Anja Feldmann

Shang-Hua Teng

Theor. Comput. Sci., 1994

On-Line Scheduling of Parallel Jobs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

1993

Optimal online scheduling of parallel jobs with dependencies.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1990

Interactive Computations of Optimal Solutions.

[BibT_eX]

[DOI]

Jan Krajícek