|
|
Close Help | ||||||||||||||
Papers are sorted roughly in the reverse order of their writing, in each of the areas:
Surveys and book chapters
K. Pruhs, E. Torng, J. Sgall:
Online scheduling
In Handbook of Scheduling: Algorithms, Models, and Performance
Analysis, ed. Joseph Y.-T. Leung, chapter 15, pages 15-1 - 15-41,
CRC Press, 2004.
J. Sgall:
Probabilistic Proofs and NP-completeness (A
Course on the PCP Theorem and its Consequences)
Technical report ITI
Series 2002-088, Charles University, Prague, 2002.
J. Sgall:
On-line scheduling
In Online Algorithms: The State of the Art, eds.A. Fiat and G.
J.
Woeginger, Lecture Notes in Comput. Sci. 1442, pages 196-231, Springer,
1998.
J. Sgall:
On-line scheduling of parallel jobs
In Proc. of the 19th Mathematical Foundations of Comput. Sci. (MFCS)
, Lecture Notes in Comput. Sci. 841, pages 159-176. Springer, 1994.
On-line and approximation algorithms, scheduling
T. Ebenlendr, J. Sgall:
A lower bound for scheduling of unit jobs with immediate decision on parallel machines
To appear in
Proc. of the 6th Workshop on Approximation and Online Algorithms
(WAOA'08), Lecture Notes in Comput. Sci. ????, pages ???,
Springer, 2009.
A preliminary version appeared as KAM-DIMATIA Series
2008-896 and ITI
Series 2008-417, Charles University, Prague, 2008.
T. Ebenlendr, J. Sgall:
Semi-online preemptive scheduling: One algorithm for all variants
To appear in Proc. of the 13th Ann. Symp. on Theor. Aspects of Comput. Sci.
(STACS), 2009.
A preliminary version appeared as KAM-DIMATIA Series
2008-895 and ITI
Series 2008-416, Charles University, Prague, 2008.
H. Bruhn, J. Cerny, A. Hall, P. Kolman, J. Sgall:
Single source multiroute flows and cuts on uniform capacity networks
Theory of Computing, 4:1–20, 2008.
T. Ebenlendr, M. Krcal, J. Sgall:
Graph balancing: A special case of scheduling unrelated parallel machines
Proc. of the 19th Ann. ACM-SIAM
Symp. on Discrete Algorithms (SODA), pages 483-490, ACM-SIAM, 2008.
J. Ding, T. Ebenlendr, J. Sgall, G. Zhang:
Online scheduling of equal-length jobs on parallel machines
Proc. of the 15th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 4698, pages 427–438. Springer, 2007.
M. Chrobak, M. Hurand, J. Sgall:
Fast algorithms for testing fault-tolerance of sequenced jobs with deadlines
To appear in J. Sched.
A preliminary version appeared in Proc. of the 28th IEEE Real-Time Systems Symposium (RTSS), pages 139–148. IEEE, 2007.
T. Ebenlendr, W. Jawor, J. Sgall:
Preemptive
Online Scheduling: Optimal Algorithms for All Speeds
To appear in Algorithmica.
A preliminary version appeared in Proc. of the 14th European Symp. on Algorithms (ESA),
Lecture
Notes
in Comput. Sci. 4168, pages 327-339, Springer, 2006.
L. Epstein, Y. Kleiman, J. Sgall, R. van Stee:
Paging with connections: FIFO strikes again
Theoretical Comput. Sci., 377(1-3): 55-64, 2007.
T. Ebenlendr, J. Noga, J. Sgall, G. Woeginger:
A note on semi-online machine covering
Proc. of the 3rd Workshop on Approximation and Online Algorithms
(WAOA'05), Lecture Notes in Comput. Sci. 3879, pages 110-118,
Springer,
2006.
J. Sgall, H. Shachnai, T. Tamir:
Fairness-Free Periodic Scheduling with Vacations
Proc. of the 13th European Symp. on Algorithms (ESA), Lecture
Notes
in Comput. Sci. 3669, pages 592-603, Springer, 2005.
M. Chrobak, P. Kolman, J. Sgall:
The greedy algorithm for the minimum common
string partition problem
ACM Trans. on Algorithms, 1(2):350-366, 2005.
A preliminary version appeared in Proc. of the APPROX, Lecture
Notes in Comput. Sci. 3122, pages 84-95, Springer, 2004.
M. Chrobak, W. Jawor, J. Sgall, T. Tichy:
Online scheduling of equal-length jobs:
Randomization and restarts help
SIAM J. Comput., 36(6):1709-1728, 2007.
A preliminary version appeared in Proc. of the 31st Int. Colloquium
on Automata, Languages, and
Programming (ICALP), Lecture Notes in Comput. Sci. 3142, pages
358-370, Springer, 2004.
M. Chrobak, W. Jawor, J. Sgall, T. Tichy:
Improved online algorithms for buffer
management in QoS switches
ACM Trans. on Algorithms, 4(3):Article No. 50, 2007.
A preliminary version appeared in
Proc. of the 12th European Symp. on Algorithms (ESA), Lecture
Notes
in Comput. Sci. 3221, pages 204-215, Springer, 2004.
M. Blaser, B. Manthey, J. Sgall:
An improved approximation algorithm for the
asymmetric TSP with strengthened triangle inequality
J. of Discrete Algorithms, 4(4):623-632,
2006.
T. Ebenlendr, J. Sgall:
Optimal and online preemptive scheduling on
uniformly related machines
To appear in J. Sched.
A preliminary version appeared in Proc. of the 21st Ann. Symp. on Theor. Aspects of Comput.
Sci. (STACS) , Lecture Notes in Comput. Sci. 2996, pages 199-210.
Springer, 2004.
F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, T.
Tichy:
Online competitive algorithms for
maximizing weighted throughput of unit jobs
J. of Discrete Algorithms, 4(2):255-276, 2006.
A preliminary version appeared in Proc. of the 21st Ann.
Symp. on Theor. Aspects of Comput. Sci. (STACS) , Lecture
Notes in Comput. Sci., pages 187-198. Springer, 2004; authors included
also Y. Bartal and R. Lavi.
M. Chrobak, J. Sgall:
Analysis of the Harmonic Algorithm for Three Servers
In Proc. of the 20th Ann. Symp. on Theor. Aspects of Comput. Sci.
(STACS)
, Lecture Notes in Comput. Sci. 2607, pages 247-259. Springer, 2003.
Unfortunately, this paper contains an error which seems to be
irrepairable.
M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tichy, N.
Vakhania:
Preemptive scheduling in overloaded systems
J. Comput. Syst. Sci., 67(1):183-197, 2003.
A preliminary version appeared in Proc. of the 29th International
Colloquium on Automata, Languages, and Programming (ICALP), Lecture
Notes in Comput. Sci. 2380, pages 800-811, Springer, 2002.
W. E. de Paepe, J. K. Lenstra, J. Sgall, R. A. Sitters, L. Stougie:
Computer-Aided Complexity Classification of
Dial-a-Ride Problems
INFORMS J. on Computing, 16(2):120-132, 2004.
M. Chrobak, J. Sgall:
Algorithms for Testing Fault-Tolerance of
Sequenced Jobs
Technical report UCR-CS-00-06, UC Riverside, 2000.
M. Chrobak, J. Csirik, C. Imreh, J. Noga, J. Sgall,
G. J. Woeginger
The buffer minimization problem for
multiprocessor scheduling with conflicts
In Proc. of the 28th International Colloquium on Automata,
Languages, and Programming (ICALP), Lecture Notes in Comput. Sci.
2076, pages 862-874, Springer, 2001.
M. Chrobak, J. Sgall:
The weighted 2-server problem
Theoretical Comput. Sci., 324(2-3):289-319, 2004.
A preliminary version appeared in Proc. of the 17th Ann. Symp. on
Theor. Aspects of Comput. Sci. (STACS)
, Lecture Notes in Comput. Sci. 1770, pages 593-604. Springer, 2000.
M. Chrobak, J. Sgall:
A simple analysis of the harmonic algorithm for
two servers
Inf. Process. Lett., 75(1-2):75-77, 2000.
Y. Azar, O. Regev, J. Sgall, G. J. Woeginger:
Off-line temporary tasks assignment
Theoretical Comput. Sci., 287(2):419-428, 2002.
L. Epstein, J. Sgall:
A lower bound for on-line scheduling on
uniformly related machines
Oper. Res. Lett., 26(1):17-22, 2000.
L. Epstein, J. Sgall:
Approximation schemes for scheduling on
uniformly related and identical parallel machines
Algorithmica, 39(1):43-57, 2004.
A preliminary version appeared in Proc. of the 7th European Symp.
on Algorithms (ESA), Lecture Notes
in Comput. Sci. 1643, pages 151-162, Springer, 1999.
S. Seiden, J. Sgall, G. J. Woeginger:
Semi-online scheduling with decreasing job
sizes
Oper. Res. Lett., 27(5):215-221, 2000.
L. Epstein, J. Noga, S. Seiden, J. Sgall, G. J. Woeginger:
Randomized online scheduling on two uniform
machines
J. of Scheduling, 4(2):71-92, 2001.
A preliminary version appeared in Proc. of the 10th Ann. ACM-SIAM
Symp. on Discrete Algorithms (SODA)
, pages 317-326, ACM-SIAM, 1999.
A. Avidor, Y. Azar, J. Sgall:
Ancient and new algorithms for load balancing
in the Lp norm
Algorithmica, 29(3):422-441, 2001.
A preliminary version appeared in Proc. of the 9th Ann. ACM-SIAM
Symp. on Discrete Algorithms (SODA)
, pages 426-435. ACM-SIAM, 1998.
Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, L.
Stougie:
Multiprocessor scheduling with rejection
SIAM J. Disc. Math., 13(1):64-78, 2000.
A preliminary version appeared
in Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA)
, pages 95-103. ACM-SIAM, 1996.
J. Sgall:
A lower bound for randomized on-line
multiprocessor scheduling
Inf. Process. Lett., 63(1):51-55, 1997.
A. Feldmann, B. Maggs, J. Sgall, D. D. Sleator, A. Tomkins:
Competitive analysis of call admission
algorithms that allow delay
Technical report CMU-CS-95-102, Carnegie-Mellon University, 1995.
J. Sgall:
Randomized on-line scheduling of parallel
jobs
J. of Algorithms, 21:149-175, 1996.
A preliminary version appeared in Proc. of the 3rd Israel Symp. on
Theory of Computing and Systems (ISTCS)
, 241-150, IEEE, 1995.
J. Sgall:
On-Line Scheduling on Parallel Machines. PhD thesis.
Technical report CMU-CS-94-144, Carnegie-Mellon University, Pittsburgh,
PA,
U.S.A., 1994.
A. Feldmann, M.-Y. Kao, J. Sgall, S.-H. Teng:
Optimal online scheduling of parallel jobs
with dependencies
J. of Combinatorial Optimization, 1(4):393-411, 1998.
A preliminary version appeared in Proc. of the 25th Ann. ACM Symp.
on Theory of Computing (STOC), pages 642-651. ACM, 1993.
A. Feldmann, J. Sgall, S.-H. Teng:
Dynamic scheduling on parallel machines
Theoretical Comput. Sci., 130(1):49-72, 1994.
A preliminary version
appeared in Proc. of the 32nd Ann. IEEE Symp. on Foundations of
Computer
Sci. (FOCS), 111-120, IEEE, 1991.
Complexity and combinatorics
D. Kral, T. Tichy, J. Sgall:
Randomized Strategies for the Plurality Problem
Discrete Applied Mathematics,156(17):3155-3338, 2008.
J. Sima, J. Sgall:
On the Non-Learnability of a Single Spiking
Neuron
Neural Computation,17(12):2635-2647,
2005.
T. Feder, P. Hell, D. Kral, J. Sgall:
Two algorithms for general list matrix
partitions
In Proc. of the 16th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA), 870-876, ACM-SIAM, 2005.
A. Bagchi, A. Chaudhary, P. Kolman, J. Sgall:
A simple combinatorial proof of duality of
multiroute flows and cuts
KAM-DIMATIA Series
2004-662 and ITI
Series 2004-186, Charles University, Prague, 2004.
D. Kral, J. Sgall:
Coloring graphs from lists with bounded size of
their union
J. of Graph Theory, 49(3):177-186, 2005.
E. Fisher, I. Newman, J. Sgall:
Functions that have read-twice constant width
branching programs are not necessarily testable
Random Structures and Algorithms, 24(2):175-193, 2004.
G. J. Woeginger, J. Sgall:
The complexity of coloring graphs without
long induced paths
Acta Cybernetica, 15(1):107-117, 2001.
J. Sgall:
Bounds on pairs of families with restricted
intersections
Combinatorica, 19(4):555-566, 1999.
P. Savicky, J. Sgall:
DNF tautologies with a limited number of
occurrences of every variable
Theoretical Comput. Sci., 238(1-2):495-498, 2000.
R. Impagliazzo, P. Pudlak, J. Sgall:
Lower bounds for the polynomial calculus and
the Groebner basis algorithm
Comput. Complexity, 8(2):127-144, 1999.
P. Pudlak, J. Sgall:
Algebraic models of computation and
interpolation for algebraic proof systems
In Proof Complexity and Feasible Arithmetic, ed. P. W. Beame
and S.
R. Buss, DIMACS Series in Discrete Mathematics and Theor. Comp. Sci.,
volume
39, pages 279-296, AMS, 1998.
S. Buss, R. Impagliazzo, J. Krajicek, P. Pudlak, A.
A. Razborov, J.Sgall:
Proof complexity in algebraic systems and bounded
depth Frege systems with modular counting
Comput. Complexity, 6(3):256-298, 1996/1997.
C. Damm, S. Jukna, J. Sgall:
Some bounds for multiparty communication
complexity of pointer jumping
Comput. Complexity, 7(2):109-127, 1998.
A preliminary version appeared
in Proc. of the 13th Ann. Symp. on Theor. Aspects of Comput. Sci.
(STACS), Lecture Notes in Comput. Sci. 1046, pages 643-654. Springer, 1996.
P. Pudlak, J. Sgall:
An upper bound for a communication game
related
to space-time tradeoffs
In The Mathematics of Paul Erdos, volume I, eds. Ronald L.
Graham and
Jaroslav Nesetril, pages 393-399. Springer, 1996.
P. Pudlak, V. Rodl, J. Sgall:
Boolean circuits, tensor ranks and
communication complexity
SIAM J. Comput., 26(3):605-633, 1997.
J. Sgall:
Solution of a covering problem related to
labelled tournaments
J. of Graph Theory, 23(2):111-118, 1996.
J. Edmonds, R. Impagliazzo, S. Rudich, J. Sgall:
Communication complexity towards lower bounds
on circuit depth
Comput. Complexity, 10(3):210-246, 2001/2002.
A preliminary
version appeared in Proc. of the 32nd Ann. IEEE Symp. on
Foundations of
Computer Sci. (FOCS), pages 249-257. IEEE, 1991.
J. Krajicek, P. Pudlak, J. Sgall:
Interactive computations of optimal solutions
In Proc. of the 15th Mathematical Foundations of Comput. Sci. (MFCS)
, Lecture Notes in Comput. Sci. 452, pages 48-60. Springer, 1990.
I. Kriz, J. Sgall:
Well-quasi-ordering depends on labels
Acta Scientarium Mathematicarum, 55:55-69, 1991.
G. J. Woeginger, J. Sgall:Other areas
J. Sgall, G. J. Woeginger:
A lower bound for cake cutting
In Proc. of the 11th Ann. European Symp. on Algorithms (ESA),
Lecture Notes in Comput. Sci. 2832, pages 459-469, Springer, 2003.
D. Kral, V. Majerech, T. Tichy, J. Sgall, G. J. Woeginger:
It is tough to be a plumber
Theoretical Comput. Sci., 313(3):473-484, 2004.
J. Sgall:
A solution of David Gale's man and lion
problem
Theoretical Comput. Sci., 259(1-2):663-670, 2001.
E. Anderson, M. Chrobak, J. Noga, J. Sgall, G. J. Woeginger:
Solution of a problem in DNA computing
Theoretical Comput. Sci., 287(2):387-391, 2002.
O. Berkman, M. Parnas, J. Sgall:
Efficient dynamic traitor tracing
SIAM J. Comput., 30(6):1802-1828, 2001.
A preliminary version appeared in Proc. of the 11th Ann. ACM-SIAM
Symp. on Discrete Algorithms (SODA), 586-595, ACM-SIAM, 2000.
D. Boneh, C. Dunworth, Richard J. Lipton, J. Sgall:
Making DNA computers error resistant
DNA Based Computers II (Princeton University, NJ, 1996),
163-170, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 44, Amer.
Math. Soc., Providence, RI, 1999.
D. Boneh, C. Dunworth, Richard J. Lipton, J. Sgall:
On the computational power of DNA
Discrete Applied Mathematics, 71:79-94, 1996.
J. Sgall, A. Sochor:
Revealed automorphisms
Commentationes Mathematicae Universitatis Carolinae,
32(1):105-113, 1991.
J. Sgall, A. Sochor:
Forcing in the alternative set theory II
Commentationes Mathematicae Universitatis Carolinae, 32(2):339-353,
1991.
J. Sgall:
Forcing in the alternative set theory I
Commentationes Mathematicae Universitatis Carolinae,
32(2):323-337, 1991.
J. Sgall, J. Witzany:
Dimension of indiscernibility equivalences
Commentationes Mathematicae Universitatis Carolinae,
28(3):537-547, 1987.
J. Sgall:
Construction of the class FN
Commentationes Mathematicae Universitatis Carolinae,
27(3):435-436, 1986.
M. Platek, J. Sgall, P. Sgall:
A dependency base for a linguistic description
In Contributions to Functional Syntax, Semantics Language
Comprehension. Benjamins, 1984.
(last update: November 2008)
