M. J. Golin -- Publications by
Date
This file contains a list of most of my publications sorted
by publication date. You can also view the publications
classified by subject. If you would like a copy
of any paper that is not available on this page please send me email at
golin@cs.ust.hk.
To Appear
- Bein, W, Golin, M., Larmore, L. and Zhang, Y. `` The
Knuth-Yao Quadrangle Inequality Speedup is a Consequence of Total
Monotonicity,'' (Preprint) PDF To appear in the ACM Transactions on Algorithms.
Conference version appeared in The 2006 ACM-SIAM Symposium on
Discrete Algorithms (SODA'06).
- Bar-Noy, A., Golin, M. and Zhang, Y. ``Online
Dynamic Programming Speedups, to appear in Theory of Computing Systems
(invited special issue for WAOA'06) papers. (Preprint)
PDF Conference version
appeared in WAOA'06
2009
- Golin, M. Xu, X . and Yu, J. ``A Generic Top-Down Dynamic
Programming Approach to Prefix-Free Codes'', The Proceedings of The ACM-SIAM Symposium on
Discrete Algorithms (SODA'09) (2009)
PDF
- Cheung, Y.K., Flajolet, Philippe, Golin, M and Lee,
C.Y., `` Multidimensional Divide-and-Conquer and Weighted Digital
Sums'', Proceedings of ANALCO 2009
PDF
2008
- Golin M., and Li, J. ``More Efficient Algorithms and
Analyses for Unequal Letter Cost Prefix-Free Coding'',
IEEE Transactions on Information Theory. 54(8) 3412-3424
(Preprint) PDF Conference version
appeared in ISAAC'07.
- Yong. X.R., Zhang Y.P. and
Golin, M. ``The Number of Spanning Trees in a Class of Double Fixed-step
Loop Networks'', Networks, 52(2) 69-77 (2008) (Preprint)
PDF
2007
- Golin M., and Li, J. ``More Efficient Algorithms and
Analyses for Unequal Letter Cost Prefix-Free Coding'',
The Proceedings of ISAAC'07. 329-340 (2007)
- Golin, M., and Zhang, Y., ``The Two-Median Problem
on Manhattan Meshes'', Networks. 49(3) 226-233
(May 2007) PDF
- Bar-Noy, A., Feng Y., and Golin, M, ``Paging
Mobile Users Efficiently and Optimally,'' in the Proceedings of the
IEEE INFOCOM'07 PDF
- Golin, M., Yong. X.R., Zhang Y.P.,
``The Asymptotic Number of Spanning Trees in Circulant Graphs,'' The
Proceedings of the The Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO07)
2006
- Fleischer, R., Golin, M. and , Zhang Y.,
``Online Maintenance of K-Medians and K-Covers on a Line,'' Algorithmica
45(4) 549-567 (2006) (Preprint)
PDF.
- Bar-Noy, A, Golin, M and Zhang Y., ``Online Dynamic
Programming Speedups'', The Proceedings of the Fourth
Workshop on Approximation and Online Algorithms (WAOA 2006), 43-54
PDF
- Golin M., Leung, Y.C, and Wang, Y.J., ``Permanents of
Circulants: a Transfer Matrix Approach'' (long version with appendix),
in The Proceedings
of the The Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO06)
PDF
- Bein, W, Golin, M., Larmore, L. and Zhang, Y. `` The
Knuth-Yao Quadrangle Inequality Speedup is a Consequence of Total
Monotonicity,'' the Proceedings of The ACM-SIAM Symposium on
Discrete Algorithms (SODA'06) (2006), pp. 31-40
PDF
2005
-
Yong. X.R., Zhang Y.P. and
Golin M. ``Chebyshev polynomials and spanning tree formulas for circulant
and related graphs," Discrete Mathematics 298 (2005) 334 – 364
(special issue for papers from FPSAC'02)
PDF conference versions
with some of this material appeared in Mathematics and Computer Science II:
Algorithms, Trees, Combinatorics and Probabilities (Proceedings of The
International Colloquium on Mathematics and Computer Science, Versailles,
France, September 16-19, 2002) and the 14th International Conference on
Formal Power Series and Algebraic Combinatorics (FPSAC 2002)
-
Golin M., and Liu, Z., "The
Structure of Optimal Prefix-Free Codes in Restricted Languages:
the Uniform Probability Case (Extended Abstract),"
in
Proceedings of the 2005 Workshop on Algorithms and Data Structures (WADS'05).
August 2005, 372-384, LNCS 3608. PDF
(Wads Version) PDF
(WADS version + extra diagrams)
-
Golin, M. and Na, H.,
``Generalizing
the Kraft-McMillan Inequality to Restricted Languages (Extended Abstract),'' in Proceedings of the 2005 IEEE Data Compression Conference, DCC'2005.
March 2005
PS
-
Golin, M. Leung Y.C., Wang Y.J.
and Yong X.R., ``Counting Structures in Grid-Graphs, Cylinders and Tori using
Transfer Matrices: Survey and New Results,'' in The Proceedings of
the The Second Workshop on Analytic Algorithmics and Combinatorics (ANALCO05)
PDF
- Cheng, S.W., Funke, A.S., Golin, M, Kumar, A.P.,
Poon, S.H., Ramos, A.E.A., ``Curve Reconstruction from Noisy Samples,'' Computational Geometry: Theory and Applications,
(special
issue for papers in SCOCG'2003) 2005 (31) 63-100
PDF conference version appeared in the 2003 ACM Symposium on
Computational Geometry (SoCG'2003)
2004
- Golin, M. Leung Y.C. and Wang Y.J., ``Counting Spanning
Trees and Other Structures in
Non-Constant-Jump Circulant Graphs,'' The Proceedings of
ISAAC'04. 2004, 508-521. PDF
- Golin, M. and Leung Y.C., ``Unhooking Circulant
Graphs:A Combinatorial Method for Counting Spanning Trees and Other
Parameters,'' The Proceedings of WG'04. 296-307.
PDF. An expanded version also appears
as HKUST TCSC technical report
HKUST-TCSC-2004-02
- Fleischer, R., Golin, M. and , Zhang Y.,
``Online Maintenance of K-Medians and K-Covers on a Line,'' Proceedings of
the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04). 2004.
PDF An expanded version also
appears as HKUST TCSC technical report
HKUST-TCSC-2004-03
- Golin, M. and Ma K.K. ``Algorithms for Infinite
Huffman-Codes,'' Proceedings of the ACM-SIAM Symposium on Discrete
Algorithms (SODA'04). 2004 Preprint(PDF)
Soda Talk(ps) An
expanded version also appears as HKUST TCSC technical report
HKUST-TCSC-2004-07
- Biedl, T., Chan, T., Demaine, E.D., Fleischer, R., Golin,
M., King J.A. and Munro, I., ``Fun-Sort--or the Chaos of Unordered
Binary Search,'' Discrete Applied Mathematics.
2004 (144) 231-236. PDF conference version
appeared in Proceedings of the 2nd International Conference `FUN with
Algorithms' (FUN-01) May 29-31, 2001
- Golin, M., Yong, X.R., Zhang, Y.P. and Sheng, L., ``New
Upper and Lower Bounds on the Channel Capacity of Read/Write Isolated
Memory,'' Discrete Applied Mathematics. 2004 (140) 35-48.
Preprint(PDF)
- Ahn, H-K,
Cheng, S.W. , Choeng,
O, Golin, M and Oostrum, R. van, "Competitive
facility location: the Voronoi game,"
Theoretical Computer Science,
(310)
1-3, January 2004, Pages 457-467 Preprint(PDF)
- Fleischer, R., Golin, M., Lea, C.T.,
Wong, S., ``Finding Optimal Paths in MREP Routing,'' Information Processing Letters. 2004 (89) 57-63.
PDF
2003
- Ding, C., Golin, M. and Klove, T., ``Meeting the Welch and
Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets, ''
Designs, Codes and Cryptography. 2003. (30) 73-84. Preprint(PS)
- Lea, C.T., Xie, Q., Golin, M, Fleischer, R.
"Residual Energy Routing with Reverse Energy Cost," Proceedings of IEEE
Globecom 2003. PDF
- Cheng, S.W., Funke, A.S., Golin, M, Kumar, A.P.,
Poon, S.H., Ramos, A.E.A., ``Curve Reconstruction from Noisy Samples,'' The
2003 ACM Symposium on Computational Geometry (SoCG'2003). 302-311.
PDF
- Golin, M and Na H., ``On the
Average Complexity of 3D-Voronoi Diagrams of Random Points On Convex Polytopes''
Computational Geometry: Theory and Applications. 2003. 25.
197-231. PDF
- Golin, M. and Leung Y.C. ``Recurrence Relations on Transfer
Matrices Yield Good Lower and Upper Bounds on the Channel Capacity of Some
2-Dimensional Constrained Systems,''
Poster in the 2003 IEEE Data Compression Conference (DCC2003). 2003.
PDF
- Fleischer, R., Golin, M., Lea, C.T.,
Wong, S., ``Finding Optimal Paths in MREP Routing,''. Poster in the 2003
Australian Telecommunications, Networks and Applications Conference (ATNAC03).
8 - 10 December 2003. Melbourne, Australia
2002
- Golin M, Kenyon, C. and Young, N. ``Huffman Coding
with Unequal Letter Costs'', 34th ACM Symposium on
Theory of Computing. PDF
- Golin, M and Na H., ``The Probabilistic Complexity of
the Voronoi Diagram of Points on a Polyhedron'', The 2002 ACM Symposium
on Computational Geometry (SoCG'2002). PDF
- Bradford, P., Golin, M, Larmore, L., and Rytter, W., ``
Optimal Prefix-Free Codes for Unequal Letter Costs and Dynamic Programming
with the Monge Property,'' Journal of Algorithms. 2002. 42. 277-303.
Preprint(ps)
- Fung, W.W., Golin M. and Gray, J.,
``Protection of Keys against Modification Attack,'' Quality and Reliability
Engineering International (special issue on Computer Network Security).
May-June 2002, 18, 217-230
- Golin, M., Langerman, S. and Steiger, W.,
``The Convex Hull for Random Lines in the Plane,'' Proceedings of the Japan
Conference on Discrete and Computational Geometry (JCDCG 2002). 2002.
PDF
- Golin, M. and Zhang, Y.P. ``Further
applications of Chebyshev polynomials in the derivation of spanning tree
formulas for circulant graphs,'' Mathematics and Computer Science II:
Algorithms, Trees, Combinatorics and Probabilities (Proceedings of The
International Colloquium on Mathematics and Computer Science, Versailles,
France, September 16-19, 2002). 541-552.
- Golin, M. and Zhang, Y.P., ``The number of spanning
trees in graphs related to circulant graphs,'' Poster at the 14th
International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC
2002) FPSAC02
- Yong, X.R. and Golin, M., ``Algebraic and
Combinatorial Properties of the Transfer Matrix of the 2-Dimensional (1,
infinity)-Runlength Limited constraint,'' Proceedings of The 2002 IEEE
International Symposium on Information Theory (ISIT2002). 354. 2002.
PDF
- Yong, X.R. and Golin, M., ``New Techniques for
Bounding the Channel Capacity of Read/Write Isolated Memory,'' Poster at
the 2002 IEEE Data Compression Conference (DCC2002). 482. 2002.
PDF
2001
- Siu-Ngan Choi and Golin, M. ``Lopsided Trees
I: A Combinatorial Analysis'', Algorithmica. 2001, 31, 240-290.
PDF
- Golin, M. ``A Combinatorial
Approach to Golomb Forests,'' Theoretical Computer Science. July 2001,
263(1-2), 283-304 PDF
- Biedl, T., Chan, T., Demaine, E.D., Fleischer, R., Golin,
M. and Munro, I., ``Fun-Sort,'' Proceedings of the 2nd International
Conference `FUN with Algorithms' (FUN-01) May 29-31, 2001
- Ahn, H.K., Cheng, S.W., Cheong, O., Golin, M., Oostrum, R.v.,
``Competitive Facility Location along a Highway, '' Proceedings of the 7th
International Computing and Combinatorics Conference (COCOON'01). August
20-23, 2001.
- Fung, W.W., Golin M. and Gray, J.,
``Protection of Keys against Modification Attack,'' Proceedings of
the 2001 IEEE Symposium on Security and Privacy, Oakland, California., May
13-16, 2001.
- Golin, M. and Na, H., ``Optimal prefix-free codes
that end in a specified pattern and similar problems: the uniform probability
case,'' Proceedings of the 2001 IEEE Data Compression Conference,
DCC'2001. March 2001 143-152. PDF
2000
- Zhang Y.P., Yong X.R. and Golin, M. ``The Number of
Spanning Trees in Circulant Graphs'', Discrete Mathematics, 2000, 223,
337-350. Preprint(PS).
The original final version is available at
www.springerlink.com
at
doi:10.1016/S0012-365X(99)00414-8
- Vigneron, A., Gao, L, Golin, M., Italiano, G, Li, B.,
``An Algorithm for Finding a k-Median in a Directed Tree,'' Information
Processing Letters, 2000. 74, 81-88 Preprint(PS)
- Chan, S-Z., Golin, M, A Dynamic Programming Algorithm
for Constructing Optimal ``1''-ended Binary Prefix-Free Codes'', IEEE
Transactions on Information Theory. 46 (4). July 2000. 1637-44.
PDF
- Golin, M. and Na H, ``On the Average Complexity of
3D-Voronoi Diagrams of Random Points On Convex Polytopes,'' Proceedings of
the 12th Canadian Conference on Computational Geometry (CCCG00). 2000.
127-135.
- Golin, M., Yong, X.R., Zhang, Y.P. and Sheng, L., ``New
Upper and Lower Bounds on the Channel Capacity of Read/Write Isolated
Memory,'' Proceedings of The 2000 IEEE International Symposium on
Information Theory (ISIT2000). 280
1999
- Golin, M. and Schuster, A. ``Optimal Point-to-Point
Broadcast Algorithms via Lopsided Trees,'' Discrete Applied Mathematics.
1999, 93, 233-263
- Arya, S., Golin, M. and Mehlhorn, K. ``On the Expected
Depth of Random Circuits,'' Combinatorics, Probability and Computing.
1999, 8, 209-222. PS
- Bo Li, M. Golin, G. Italiano, X. Deng and A. K. Sohraby `On The
Optimal Placement of Web Proxies in the Internet,'' IEEE Infocom'99.
PDF
1998
- Golin, M. and Rote, G., ``A
Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for
Unequal Letter Costs," IEEE Transactions on Information Theory,
September 1998, 44(5), 1770-1781. PDF
- M . Golin, R. Raman, C.
Schwarz and M. Smid, ``Randomized Data Structures for the Dynamic Closest Pair
Problem,'' Siam Journal on Computing , August, 1998, 27(4), 1036-1072.
PS
- M . Golin, and S. Zaks, ``Labelled
Trees and Pairs of Input-Output Permutations in Priority Queues,''
Theoretical Computer Science, 1998, 205, 99-114.
- Devillers, O. and Golin, M., "Dog Bites Postman:
Point Location in the Voronoi Diagram and Related Problems", International
Journal of Computational Geometry and Applications, 8(3), 321-342, 1998.
- Li, B., Deng, X., Golin, M and Sohraby, ``Dynamic and
Distributed Web Caching in Active Networks,'' Asia Pacific Web Conference
(APWeb'98). 27-30 September. Beijing, China. 1998
- Chow, T. and Golin, M., ``Convergence and Construction of
Minimal-Cost Infinite Trees,'' The 1998 IEEE International Symposium on
Information Theory (ISIT98). 227. August 1998.
- Chan, S-Z., Golin, M, A Dynamic Programming Algorithm
for Constructing Optimal ``1''-ended Binary Prefix-Free Codes,'' The 1998
IEEE International Symposium on Information Theory (ISIT98). 45. August
1998.
- Bradford, P., Golin, M, Larmore, L., and Rytter, W., ``
Optimal Prefix-Free Codes for Unequal Letter Costs and Dynamic Programming
with the Monge Property,'' Sixth European Symposium on Algorithms (ESA'98)
(LNCS 1461). 43-54. 1998
1997
- Golin, M. and Schuster, A. ``Optimal Point-to-Point
Broadcast Algorithms via Lopsided Trees,'' Fifth Israeli Symposium on
Theory of Computing and Systems (ISTCS'97). 63-73.1997.
- Golin, M. ``A Combinatorial Approach to Infinite
Prefix-free Codes,'' International Workshop on Combinatorics and Computer
Science (10th Franco-Japanese and 5th Franco-Chinese Conference), Ecole
Polytechnique, Palaiseau, France. September 15-18, 1997
1996
- Golin, M. ``Limit Theorems for
Minimum-Weight Triangulations, Other Euclidean Functionals and Probabilistic
Recurrence Relations,'' Proceedings of The Seventh Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA '96) , January 1996.
PDF
- Golin, M. and Young, N.,
"Prefix Codes: Equiprobable Words, Unequal Letter Costs," SIAM Journal on
Computing, 25(6), pp. 1281-1292, December 1996.
- Devillers, O., Golin, M., Kedem, K.,
Schirra, S., ``Queries on Voronoi Diagrams of Moving Points,''
Computational Geometry: Theory and Applications. 6. 1996. 315-327
- Choi, S-N., Golin, M., ``Lopsided trees:
Algorithms, Analyses and Applications,'' Proceedings of the 23rd
International Colloquium on Automata Languages and Programming (ICALP '96).
538-549. July 1996
1995
- Devillers, O. and Golin, M., ``Incremental Algorithms for
the Construction of Convex Hulls of Circles and Lower Envelopes of
Parabolas,'' Information Processing Letters. 56(3). 1995. 157-164
- Golin M., Raman, R., Schwarz, C., Smid,
M., ``A Simple Randomized Closest Pair Algorithm,'' Nordic Journal on
Computing. 2 1995. 3-27 Preprint
(PS)
- Golin, M., Supowit, K.J., ``Newton's Method for
Quadratics and Nested Intervals,'' Complex Systems. 8. 1994. 161-180
- Cheng, S.W., Golin, M. and Tsang, J., ``Expected Case
Analysis of Beta Skeletons with Applications to the Heuristic Construction of
Minimum Weight Triangulations,'' Proceedings of the 7th Canadian Conference
on Computational Geometry. 1995
- Golin, M. and Rote, G., ``A
Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for
Unequal Letter Costs," Proceedings of the 22nd International
Colloquium on Automata Languages and Programming (ICALP '95). 256-267.
July 1995.
1994
- Flajolet,P. and Golin,M., "Mellin Transforms and
Asymptotics: The Mergesort Recurrence," Acta Informatica, 31, pp.
673-696, 1994. Preprint(ps)
- Golin, M., "A Provably-Fast,
Linear-Expected-Time, Maxima-Finding Algorithm," Algorithmica, 11, pp.
501-524, 1994.
- Devillers, O. and Golin, M., ``Incremental Algorithms for
the Construction of Convex Hulls of Circles and Lower Envelopes of Parabolas,'
Proceedings of the 6th Canadian Conference on Computational Geometry.
1994.
- Devillers, O., Golin, M., Kedem, K.,
Schirra, S., ``Queries on Voronoi Diagrams of Moving Points,''
Proceedings of the 6th Canadian Conference on Computational Geometry. 1994
- M . Golin, and S. Zaks, ``Labelled Trees and Pairs of
Input-Output Permutations in Priority Queues,'' Proceedings of the
International Workshop on Graph-theoretic Concepts in Computer Science (WG94).
Munich, Germany. 282-291. June 1994.
- Golin, M. and Young, N.,
"Prefix Codes: Equiprobable Words, Unequal Letter Costs,"
Proceedings of the 21st International Colloquim on Automata Languages and
Programming (ICALP '94). Jerusalem, Israel. 605-617. July 1994
1993
- Golin, M., "How Many Maxima
Can There Be?," Computational Geometry: Theory and Applications, 2,
pp. 335-353, 1993. PDF
- Golin, M. and Sedgewick R., ``Queue-Mergesort,''
Information Processing Letters, 48, 253-259.
- Golin, M., "Maxima in Convex
Regions", Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'93),
pp.352-360, 1993.
- Golin, M. and Flajolet, P., ``Exact Asymptotics of
Divide-and-Conquer Recurrences,'' Proceedings of the 20th International
Colloquim on Automata Languages and Programming (ICALP '93),'' Lund,
Sweden. 137-149. July 1993.
- Golin M., Raman, R., Schwarz, C., Smid,
M., ``A Simple Randomized Closest Pair Algorithm,'' Proceedings of the
Fifth Canadian Conference on Computational Geometry. 1993
- Devillers, O. and Golin, M., ``Dog Bites Postman:
Point Location in the Voronoi Diagram and Related Problems,'' Proceedings
of the First Annual European Symposium on Algorithms (ESA '93). 133-144.
1993
- M . Golin, R. Raman, C.
Schwarz and M. Smid, ``Randomized Data Structures for the Dynamic Closest Pair
Problem,''Proceedings of the Fourth Annual Symposium on Discrete Algorithms
(SODA '93). 301-310. 1993 PDF
1992
- M . Golin, C.
Schwarz and M. Smid, ``Further Dynamic Computational Geometry,''
Proceedings of the Fourth Canadian Conference on Computational Geometry.
154-159. 1992
- M. Golin, ``Dynamic Closest Pairs: A Probabilistic
Approach,'' Proceedings of the Third Scandinavian Workshop on Algorithm
Theory (SWAT '92). 340-35. 1992
1988
- Golin, M. and Sedgewick, R., ``Analysis of a Simple but
Efficient Convex Hull Algorithm,'' Proceedings of the Fourth Annual
Symposium on Computational Geometry. 153-163. 1988
- Golin, M. and Sedgewick, R., ``Exact Analysis of Mergesort,''
Presented at the Fourth SIAM Conference on Discrete Mathematics (1988)
Return to home page
www.cs.ust.hk/~golin.
Last updated
10/08/2009 01:40 PM +0800