EDBT 2026 Demo / reviewers in the wild / expert
Kin-Shing Liu
dblp:80/520
· DBLP profile ↗
4ranked-venue papers
0as first author
0since 2021 · last 2008
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 4
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
2 papers |
Approximation and online algorithms · 56% Mathematical optimization · 31% Algorithms and data structures · 12% |
Topics — the 7 heaviest of 7, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Approximation and online algorithms › online algorithms
competitive analysis |
0.1 | 2 | 2008 | Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling · SIAM J. Comput. 2008 Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling · SODA 2006 |
Mathematical optimization › scheduling
flow time scheduling |
0.1 | 2 | 2008 | Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling · SIAM J. Comput. 2008 Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling · SODA 2006 |
Approximation and online algorithms › online algorithms
online scheduling |
0.1 | 1 | 2008 | Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling · SIAM J. Comput. 2008 |
Algorithms and data structures › analysis of algorithms › beyond worst-case analysis
resource augmentation |
0.1 | 1 | 2008 | Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling · SIAM J. Comput. 2008 |
Approximation and online algorithms › online algorithms › online scheduling
weighted flow time |
0.1 | 1 | 2008 | Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling · SIAM J. Comput. 2008 |
Approximation and online algorithms
online algorithms |
0.1 | 1 | 2006 | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling · SODA 2006 |
Mathematical optimization
scheduling |
0.1 | 1 | 2006 | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling · SODA 2006 |
Methods — techniques the papers use, named apart from their topics
highest density first · 0.1extra machines · 0.1SRPT · 0.1machine augmentation · 0.1competitive ratio analysis · 0.1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2008 | Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time SchedulingabstractWe study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate for the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using $O(1)$ times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [C. A. Phillips et al., in Proceedings of STOC, ACM, New York, 1997, pp. 140–149] and stretch [W. T. Chan et al., in Proceedings of MFCS, Springer-Verlag, Berlin, 2005, pp. 236–247] and HDF (highest density first) is $O(1)$-competitive for weighted flow time [L. Becchetti et al., in Proceedings of RANDOM-APPROX, Springer-Verlag, Berlin, 2001, pp. 36–47]. Using extra unit-speed machines instead of faster machines to achieve competitive performance is more challenging, as a faster machine can speed up a job but extra unit-speed machines cannot. This paper gives a nontrivial relationship between the extra-speed and extra-machine analyses. It shows that competitive results via faster machines can be transformed to similar results via extra machines, hence giving the first algorithms that, using $O(1)$ times unit-speed machines, are 1-competitive for flow time and stretch and $O(1)$-competitive for weighted flow time. Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu |
SIAM J. Comput. | 3 |
| 2006 | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu |
SODA | 3 |
| 2006 | New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling
Wun-Tat Chan, Tak Wah Lam, Kin-Shing Liu, Prudence W. H. Wong |
Theor. Comput. Sci. | 3 |
| 2005 | New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling
Wun-Tat Chan, Tak Wah Lam, Kin-Shing Liu, Prudence W. H. Wong |
MFCS | 3 |