Savio Tse
Last Updated on October 2015
My email address:
sshtse@cs.hku.hk
Publications in Journals
-
S.S.H. Tse,
"Belated Analyses of Three Credit-Based Adaptive Polling Algorithms",
International Journal of Foundations of Computer Science,
to appear.
-
O. Dagdeviren, K. Erciyes, and Savio Tse,
"Semi-asynchronous and distributed weighted connected dominating
set algorithms for wireless sensor networks",
Computer Standards and Interfaces,
Vol. 42, November 2015, 143-156.
-
S.S.H. Tse,
"Online Balancing Two Independent Criteria upon
Placements and Deletions",
IEEE Transactions on Parallel and Distributed Systems,
vol. 24, No. 8, August 2013, 1644-1650.
Remarks:
It is the first result in the literature of the context as the
title promises.
An intuitive and common way for balancing two criteria, namely
load and storage space, is to reduce
the loads (resp. storage spaces) of the highest-load
(resp. highest-storage-space) entities;
however, we only keep the load (resp. storage space)
of a certain entity large enough.
This counter-intuitive way is for keeping the online property,
and it deserves a proof which consists of 14 lemmas and one theorem.
Moreover, the process of balancing two criteria is a kind of
breaking the equivalence of exchange in between.
-
S.S.H. Tse,
"Online Bounds on Balancing Two Independent Criteria with
Replication and Reallocation",
IEEE Transactions on Computers,
vol. 61, No. 11, November 2012, 1601-1610.
Remarks:
This paper reveals the power of replication and reallocation
in the context of online bicriteria load balancing upon placement.
It proves that allowing one more replica for each object, or
very little amount of reallocation, can make strict improvements.
Following the suggestion of one reviewer,
a brief survey has been done in the introduction.
Correction:
The expression M - t_l in the load bound of the second result
should be M - 2t_l + 1, where t_l \leq \frac{M+1}{2}. It is a careless mistake.
-
S.S.H. Tse,
"Online Bicriteria Load Balancing using Object Reallocation",
IEEE Transactions on Parallel and Distributed Systems,
vol. 20, No. 3, March 2009, 379-388.
-
Y. Shi, F.C.M. Lau, S.S.H. Tse, Z.H. Du,
R.C. Tang, and S.L. Li,
"Club Theory of the Grid",
Concurrency and Computation: Practice and Experience,
vol. 18, Issue 14, December 2006, 1759-1773.
-
S.S.H. Tse,
"A short note on the Lower Bound of Dilation
for O(log n)-label Interval Routing",
Information Processing Letters,
vol. 95, Issue 2, July 2005, 351-353.
-
S.S.H. Tse,
"Approximate Algorithms for Document Placement
in Distributed Web Servers",
IEEE Transactions on Parallel and Distributed Systems,
vol. 16, No. 6, June 2005, 489-496.
(Corrigendum)
-
S.S.H. Tse and F.C.M. Lau,
"New Bounds for Multi-Label Interval Routing",
Theoretical Computer Science, Vol. 310, No. 1-3, 2004, 61-77.
(Corrigendum)
-
F.C.M. Lau, P.K.W. Cheng and S.S.H. Tse,
"An Algorithm for the 2-Median Problem on Two-Dimensional Meshes",
The Computer Journal, vol. 44, No. 2, 2001, 101-108.
-
S.S.H. Tse and F.C.M. Lau,
"On the Complexity of Some Adaptive Polling Algorithms in General
Networks",
International Journal of Foundations of Computer Science
(Special Issue on Graph Algorithms and Applications),
vol. 10, No. 2, 1999, 211-224.
Remarks:
It had not been an SCI-Expanded journal when this paper was
published, but I like this paper the most. The technique used
in the lower bound proof is a fooling algorithm, and it rescues
the codes from any trap of repetitions. This work has been
done since 1992 Summer, and is my first research work.
-
S.S.H. Tse and F.C.M. Lau,
"On the Space Requirement of Interval Routing",
IEEE Transactions on Computers, vol. 48, No. 7, July 1999,
752-757.
(Corrigendum)
-
S.S.H. Tse and F.C.M. Lau,
"More on the Efficiency of Interval Routing",
The Computer Journal , vol. 41, No. 4, 1998, 238-242.
-
S.S.H. Tse and F.C.M. Lau,
"A Lower Bound for Interval Routing in General Networks",
Networks, Vol. 29, No. 1, January 1997, 49-53.
(Corrigendum)
Publications in Conferences and Workshops
-
S.S.H. Tse,
``Online Bicriteria Load Balancing with Replication in Amortized Logarithmic Time'',
Proceedings of IADIS Applied Computing 2013,
Fort Worth, Texas, USA, October 23-25, 2013.
-
S.S.H. Tse,
``Bicriteria Load Balancing for Online Placement in Heterogeneous Servers
with Pareto Upper Bounds'',
Proceedings of The 11th IEEE International Symposium on Parallel and
Distributed Processing with Applications (ISPA 2013),
Melbourne, Australia, July 16-18, 2013.
-
S.S.H. Tse,
``Rotating Escalators upon Deletions for Improving Online Bicriteria
Load Balancing'',
Proceedings of 2012 International Symposium on Pervasive Systems,
Algorithms, and Networks, San Marcos, Texas, USA, December 13-15, 2012.
-
S.S.H. Tse, J.P. Zhou, and F.C.M. Lau,
``Fault-tolerant Routing for Irregular Faulty Patterns in 2D-Mesh without
Virtual Channel'',
Proceedings of 2012 International Symposium on Pervasive Systems,
Algorithms, and Networks, San Marcos, Texas, USA, December 13-15, 2012.
-
M. Cokyilmaz, S. Kalafat, E. Isenkul, S.S.H. Tse, and A. Sertbas,
``Comparison Study of Particle Swarm Optimization and Differential
Evolution Methods for Solving SAT Problem using nVidia CUDA Framework'',
Proceedings of the 9th International Conference on
Electronics, Computer and Computation (ICECCO 2012),
Ankara, Turkey, November 1--3, 2012.
-
S.S.H. Tse,
``Online Balancing Two Independent Criteria'',
Lecture Notes in Computer Science 5245, 244-254,
Proceedings of The IFIP International Conference on Network
and Parallel Computing (NPC 2008),
Shanghai, China, October 18--20, 2008.
-
S.S.H. Tse,
``Online Bicriteria Load Balancing for Distributed File Servers'',
Proceedings of The Second International Conference on
Communications and Networking in China (ChinaCom 2007),
Shanghai, China, August 22--24, 2007.
-
S.S.H. Tse,
``Online Solutions for Scalable File Server Systems'',
Proceedings of the First International Conference on
Scalable Information Systems (INFOSCALE 2006),
Hong Kong, May 29--June 1, 2006.
-
S.S.H. Tse and F.C.M. Lau,
"An Approximation Solution for the 2-Median Problem on
Two-Dimensional Meshes",
Proceedings of The First International Workshop on
Information Networking and Applications (INA 2005),
Tamkang, Taiwan, March 2005.
-
S.S.H. Tse,
"Approximate Algorithms for Document Placement
in Distributed Web Servers",
Proceedings of The 7th International Symposium on
Parallel Architectures, Algorithms, and Networks (I-SPAN),
Hong Kong, China, May 2004, 61--66.
-
S.S.H. Tse and H.V. Leong,
"Mobile Data Management in Ad hoc Wireless Networks",
Proceedings of The 18th International Conference
on Advanced Information Networking and Applications (AINA 2004),
Fukuoka, Japan, March 2004, vol 2, 428--431.
-
S.S.H. Tse and F.C.M. Lau,
"An Upper Bound Result for Multi-Label Interval Routing on Planar Graphs",
Proceedings of 9th International Colloquium on
Structural Information and Communication Complexity (SIROCCO '02), Andros,
Greece, June 2002, 297-308.
-
S.S.H. Tse and F.C.M. Lau,
"Some Results on the Space Requirement of Interval Routing",
Proceedings of 6th International Colloquium on
Structural Information and Communication Complexity (SIROCCO 6), Lacanau,
France, July 1999, 264-279.
-
S.S.H. Tse and F.C.M. Lau,
"Adaptive Broadcast-Confirm Algorithms in General Networks
and their Analysis",
Proceedings of 5th International Colloquium on
Structural Information and Communication Complexity (SIROCCO 5), Amalfi,
Italy, June 1998, 20-35.
-
P.K.W. Cheng, F.C.M. Lau and S.S.H. Tse,
"Algorithms for the Location Problem in Linear Arrays and Rings",
Proceedings of International Symposium on
Operations Research and its Applications (ISORA'98), Kunming,
China, August 1998, 39-53.
-
P.K.W. Cheng, F.C.M. Lau and S.S.H. Tse,
"An Algorithm for the Location Problem in Two-Dimensional Meshes",
Proceedings of International Symposium on
Mathematical Foundations of Computer Science
(MFCS'98) Workshop on Communication , Brno,
Czech Republic, August 1998, 76-90.
-
S.S.H. Tse and F.C.M. Lau,
"An Optimal Lower Bound for Interval Routing in General Networks",
Proceedings of 4th International Colloquium on
Structural Information and Communication Complexity (SIROCCO'97), Ascona,
Switzerland, July 1997, 112-124.
-
S.S.H. Tse and F.C.M. Lau,
"Two Lower Bounds for Multi-Label Interval Routing."
Proceedings of
Computing: The Australasian Theory Symposium (CATS'97),
Sydney, Australia, February 1997.
-
S.S.H. Tse and F.C.M. Lau,
"Lower Bounds for Multi-Label Interval Routing."
Proceedings of 2nd
Colloquium on Structural Information & Communication Complexity
(SIROCCO'95), Olympia, Greece, June 1995, 123-134.