Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.

Kin-Shing Liu

dblp:80/520 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Approximation and online algorithms › online algorithms
competitive analysis
0.122008
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.122008
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.112008
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.112008
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.112008
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.112006
Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling · SODA 2006
Mathematical optimization
scheduling
0.112006
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
YearPublicationVenuePosition
2008 Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling
abstract
We 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
SODA3
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
MFCS3