M. J. Golin -- Publications by
Area
This file contains a list of most of my publications
classified by subject. Please note that some papers cross categories and
are listed in multiple sections. Only the most up to date versions of
a paper are listed; in particular, if a paper first appeared in a
conference and later in a journal then only the journal version would be
listed. You can also view the publications
sorted by date of publication. 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.
TOPICS
Geometry: Most of my research in
this area is in probabilistic (computational) geometry with a few results
in standard computational geometry as well.
Probabilistic Geometry:
- 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)
- 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
conference version appeared in Proceedings of
the 12th Canadian Conference on Computational Geometry (CCCG00). 2000.
127-135.
- 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
- 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. ``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
- 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., "A Provably-Fast, Linear-Expected-Time,
Maxima-Finding Algorithm," Algorithmica, 11, pp. 501-524, 1994.
- Golin, M., "How Many Maxima Can There Be?,"
Computational Geometry: Theory and Applications," 2, pp. 335-353, 1993.
PDF
- Golin, M., "Maxima in Convex Regions", Fourth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA'93), pp.352-360, 1993.
- 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
Computational geometry:
- 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.
- 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 conference
version appeared in Proceedings of the Fourth Annual Symposium on Discrete
Algorithms (SODA '93). 301-310. 1993
PDF
- 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. conference
version appeared in Proceedings of the First Annual European Symposium on
Algorithms (ESA '93).
- Devillers, O., Golin, M., Kedem, K., Schirra, S.,
``Queries on Voronoi Diagrams of Moving Points,'' Computational Geometry:
Theory and Applications. 6. 1996. 315-327. conference version
appeared in Proceedings of the 6th Canadian Conference on Computational
Geometry. 1994
- 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.
conference version appeared in Proceedings of the 6th Canadian
Conference on Computational Geometry. 1994.
- Golin M., Raman, R., Schwarz, C., Smid, M., ``A Simple
Randomized Closest Pair Algorithm,'' Nordic Journal on Computing. 2
1995. 3-27 Preprint (PS) conference version appeared in Proceedings of the Fifth
Canadian Conference on Computational Geometry. 1993
- M . Golin, C.
Schwarz and M. Smid, ``Further Dynamic Computational Geometry,''
Proceedings of the Fourth Canadian Conference on Computational Geometry.
154-159. 1992
Tree Structures: Much of my research in
this area revolves around prefix codes which can be represented using trees.
Some of my early work also dealt with analysis of mergesort (via the analysis of
its merge tree).
Prefix Codes:
- 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
- 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.
- 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),''
to appear in Proceedings of the 2005 IEEE Data Compression Conference,
DCC'2005. March 2005
PDF
- 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.
- Golin M, Kenyon, C. and Young, N. ``Huffman Coding
with Unequal Letter Costs'', 34th ACM Symposium on Theory of Computing.
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) conference
version appeared in Sixth European Symposium on Algorithms (ESA'98) (LNCS
1461). 43-54. 1998
- 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 conference
version appeared in International Workshop on Combinatorics and Computer
Science (10th Franco-Japanese and 5th Franco-Chinese Conference),
- 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
- 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 conference version
appeared in The 1998 IEEE International Symposium on Information Theory
(ISIT98). 45. August 1998.
- Golin, M. and Schuster, A. ``Optimal Point-to-Point
Broadcast Algorithms via Lopsided Trees,'' Discrete Applied Mathematics.
1999, 93, 233-263 conference version appeared in Fifth Israeli
Symposium on Theory of Computing and Systems (ISTCS'97). 63-73.1997.
- 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 conference version appeared
in Proceedings of the 22nd International Colloquium on Automata Languages
and Programming (ICALP '95). 256-267. July 1995.
- 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.
- Golin, M. and Young, N., "Prefix Codes: Equiprobable Words,
Unequal Letter Costs," SIAM Journal on Computing, 25(6), pp. 1281-1292,
December 1996. conference version appeared in Proceedings of
the 21st International Colloquim on Automata Languages and Programming (ICALP
'94). Jerusalem, Israel. 605-617. July 1994
Mergesort
- Cheung, Y.K., Flajolet, Philippe, Golin, M and Lee,
C.Y., `` Multidimensional Divide-and-Conquer and Weighted Digital
Sums'', Proceedings of ANALCO 2009
PDF
- Flajolet,P. and Golin,M., "Mellin Transforms and
Asymptotics: The Mergesort Recurrence," Acta Informatica, 31, pp.
673-696, 1994. Preprint(ps)
conference version appeared in ``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. and Sedgewick R., ``Queue-Mergesort,''
Information Processing Letters, 48, 253-259. 1993.
- Golin, M. and Sedgewick, R., ``Exact Analysis of
Mergesort,'' Presented at the Fourth SIAM Conference on Discrete
Mathematics (1988)
Other
Tree-Structure Related Papers
- Biedl, T., Chan, T., Demaine, E.D., Fleischer, R., Golin,
M. and Munro, I., ``Fun-Sort,'' to appear in Discrete Applied Mathematics.
PS conference version
appeared in Proceedings of the 2nd International Conference `FUN with
Algorithms' (FUN-01) May 29-31, 2001
- 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
- Arya, S., Golin, M. and Mehlhorn, K. ``On the Expected
Depth of Random Circuits,'' Combinatorics, Probability and Computing.
1999, 8, 209-222. PS
- M . Golin, and S. Zaks, ``Labelled Trees and Pairs of
Input-Output Permutations in Priority Queues,'' Theoretical Computer
Science, 1998, 205, 99-114. conference version appeared in
Proceedings of the International Workshop on Graph-theoretic Concepts in
Computer Science (WG94). Munich, Germany. 282-291. June 1994.
Combinatorics:
One large project on counting structures in circulant graphs and
a small project on calculating the capacity of two (and higher) dimensional codes. There are
also some one-off problems.
Circulant Graphs
- 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
- Golin, M. Yong. X.R., Zhang Y.P.,
``The Asymptotic Number of Spanning Trees in Circulant Graphs,'' in The
Proceedings of the The Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO07)
- Golin M., Leung, Y.C, 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
- 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. 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.'' The
Proceedings of the The Second Workshop on Analytic Algorithmics and
Combinatorics (ANALCO05) PDF
- 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
- 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
- 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
Capacity of 2D Codes
- 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) conference
version appeared in Proceedings of The 2000 IEEE International Symposium on
Information Theory (ISIT2000). 280
- 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
- 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
Others
- 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)
- 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 conference version appeared in Proceedings of the
2001 IEEE Symposium on Security and Privacy, Oakland, California., May
13-16, 2001.
- M . Golin, and S. Zaks, ``Labelled Trees and Pairs of
Input-Output Permutations in Priority Queues,'' Theoretical Computer
Science, 1998, 205, 99-114. conference version appeared in
Proceedings of the International Workshop on Graph-theoretic Concepts in
Computer Science (WG94). Munich, Germany. 282-291. June 1994.
Assorted: These
are smaller problems that I have worked on that don't fit into the above areas.
Minimum Residual Energy
- Fleischer, R., Golin, M., Lea, C.T.,
Wong, S., ``Finding Optimal Paths in MREP Routing,''
Information Processing Letters. 2004 (89) 57-63.
PDF conference version appeared as poster in the
2003 Australian Telecommunications, Networks and Applications Conference
(ATNAC03).
- Lea, C.T., Xie, Q., Golin, M, Fleischer, R. "Residual
Energy Routing with Reverse Energy Cost," Proceedings of IEEE Globecom 2003.
PDF
K-Median problems
- Golin, M., and Zhang, Y., ``The Two-Median Problem
on Manhattan Meshes'', Networks. 49(3) 226-233
(May 2007) PDF
- 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. Conference
version appeared in Proceedings of
the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04). 2004.
PDF
- 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)
- 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
- Li, B., Deng, X., Golin, M and Sohraby, A.K., ``Dynamic and
Distributed Web Caching in Active Networks,'' Asia Pacific Web Conference
(APWeb'98). 27-30 September. Beijing, China. 1998
Others
- Bar-Noy, A., Feng Y., and Golin, M, ``Paging
Mobile Users Efficiently and Optimally,'' to appear in Proceedings of the
IEEE INFOCOM'07 PDF
- 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
- 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).
- 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
- 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)
- 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 conference version appeared in Proceedings of the
2001 IEEE Symposium on Security and Privacy, Oakland, California., May
13-16, 2001.
- 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) conference version appeared in
Proceedings of the 7th
International Computing and Combinatorics Conference (COCOON'01). August
20-23, 2001.
- Arya, S., Golin, M. and Mehlhorn, K. ``On the Expected
Depth of Random Circuits,'' Combinatorics, Probability and Computing.
1999, 8, 209-222. PS
- Golin, M., Supowit, K.J., ``Newton's Method for
Quadratics and Nested Intervals,'' Complex Systems. 8. 1994. 161-180
Return to home page
www.cs.ust.hk/~golin.
Last updated
10/08/2009 01:41 PM +0800