Mordecai J. Golin

According to our database, Mordecai J. Golin authored at least 112 papers between 1988 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

The Markov-Chain Polytope with Applications.

Mordecai J. Golin, Albert John Lalim Patupat

CoRR, 2024

Fully Dynamic <i>k</i>-Center in Low Dimensions via Approximate Furthest Neighbors.

Jinxiang Gan, Mordecai J. Golin

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

A (Weakly) Polynomial Algorithm for AIVF Coding.

Mordecai J. Golin, Reza Hosseini Dolatabadi, Arian Zamani

Proceedings of the IEEE International Symposium on Information Theory, 2024

Better Algorithms for Constructing Minimum Cost Markov Chains and AIFV Codes.

Mordecai J. Golin, Reza Hosseini Dolatabadi, Arian Zamani

Proceedings of the IEEE International Symposium on Information Theory, 2024

2023

Scheduling on a graph with release times.

Wei Yu, Mordecai J. Golin, Guochuan Zhang

J. Sched., December, 2023

A Polynomial Time Algorithm for Constructing Optimal Binary AIFV-2 Codes.

Mordecai J. Golin, Elfarouk Harb

IEEE Trans. Inf. Theory, October, 2023

Minmax Centered k-Partitioning of Trees and Applications to Sink Evacuation with Dynamic Confluent Flows.

Di Chen, Mordecai J. Golin

Algorithmica, July, 2023

Fair k-Center: a Coreset Approach in Low Dimensions.

Jinxiang Gan, Mordecai J. Golin, Zonghan Yang, Yuhao Zhang

CoRR, 2023

Fully Dynamic k-Center in Low Dimensions via Approximate Furthest Neighbors.

Jinxiang Gan, Mordecai J. Golin

CoRR, 2023

2022

A Simple Algorithm for Optimal Search Trees with Two-way Comparisons.

Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young

ACM Trans. Algorithms, 2022

Minmax regret for sink location on dynamic flow paths with general capacities.

Mordecai J. Golin, Sai Sandeep

Discret. Appl. Math., 2022

On Huang and Wong's algorithm for generalized binary split trees.

Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young

Acta Informatica, 2022

Speeding Up AIFV-m Dynamic Programs by m-1 Orders of Magnitude.

Mordecai J. Golin, Albert John L. Patupat

Proceedings of the IEEE International Symposium on Information Theory, 2022

2021

Speeding up the AIFV-2 dynamic programs by two orders of magnitude using Range Minimum Queries.

Mordecai J. Golin, Elfarouk Harb

Theor. Comput. Sci., 2021

Scheduling with gaps: new models and algorithms.

Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng

J. Sched., 2021

On the cost of unsuccessful searches in search trees with two-way comparisons.

Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young

Inf. Comput., 2021

2020

Polynomial Time Algorithms for Constructing Optimal Binary AIFV-2 Codes.

Mordecai J. Golin, Elfarouk Harb

CoRR, 2020

2019

The transfer matrices and the capacity of the 2-dimensional (1, ∞)-runlength limited constraint.

Zhibing Chen, Mordecai J. Golin, Xuerong Yong

Discret. Math., 2019

Minmax Regret for sink location on paths with general capacities.

Mordecai J. Golin, Sai Sandeep

CoRR, 2019

Minmax Regret k-Sink Location on a Dynamic Path Network with Uniform Capacities.

Guru Prakash Arumugam, John Augustine, Mordecai J. Golin, Prashanth Srikanthan

Algorithmica, 2019

Polynomial Time Algorithms for Constructing Optimal AIFV Codes.

Mordecai J. Golin, Elfarouk Harb

Proceedings of the Data Compression Conference, 2019

The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions.

Josep Díaz, Mordecai J. Golin

Proceedings of the Approximation, 2019

2018

Smoothed Analysis of the Expected Number of Maximal Points in Two Dimensions.

Josep Díaz, Mordecai J. Golin

CoRR, 2018

Minmax-Regret k-Sink Location on a Dynamic Tree Network with Uniform Capacities.

Mordecai J. Golin, Sai Sandeep

CoRR, 2018

Dynamic Trees with Almost-Optimal Access Cost.

Mordecai J. Golin, John Iacono, Stefan Langerman, J. Ian Munro, Yakov Nekrich

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks.

Binay Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems.

Mordecai J. Golin, Hadi Khodabande, Bo Qin

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

2016

Encoding 2D range maximum queries.

Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, Sunil M. Shende

Theor. Comput. Sci., 2016

The channel capacity of read/write isolated memory.

Chuan-Long Wang, Xuerong Yong, Mordecai J. Golin

Discret. Appl. Math., 2016

Minmax Tree Facility Location and Sink Evacuation with Dynamic Confluent Flows.

Di Chen, Mordecai J. Golin

CoRR, 2016

Improved Algorithms for Computing k-Sink on Dynamic Path Networks.

Binay K. Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh

CoRR, 2016

Optimal Evacuation Flows on Dynamic Paths with General Edge Capacities.

Guru Prakash Arumugam, John Augustine, Mordecai J. Golin, Yuya Higashikawa, Naoki Katoh, Prashanth Srikanthan

CoRR, 2016

Sink Evacuation on Trees with Dynamic Confluent Flows.

Di Chen, Mordecai J. Golin

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

2015

Multiple sink location problems in dynamic path networks.

Yuya Higashikawa, Mordecai J. Golin, Naoki Katoh

Theor. Comput. Sci., 2015

Minimax regret 1-sink location problem in dynamic path networks.

Yuya Higashikawa, John Augustine, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, Yin-Feng Xu

Theor. Comput. Sci., 2015

Optimal search trees with equality tests.

Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young

CoRR, 2015

Optimal Search Trees with 2-Way Comparisons.

Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

2014

Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity.

Yuya Higashikawa, Mordecai J. Golin, Naoki Katoh

J. Graph Algorithms Appl., 2014

Improved Algorithms for Multiple Sink Location Problems in Dynamic Path Networks.

Yuya Higashikawa, Mordecai J. Golin, Naoki Katoh

CoRR, 2014

A Polynomial Time Algorithm for Minimax-Regret Evacuation on a Dynamic Path.

Guru Prakash Arumugam, John Augustine, Mordecai J. Golin, Prashanth Srikanthan

CoRR, 2014

2013

Paging mobile users in cellular networks: Optimality versus complexity and simplicity.

Amotz Bar-Noy, Panagiotis Cheilaris, Yi Feng, Mordecai J. Golin

Theor. Comput. Sci., 2013

2012

Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme.

Mordecai J. Golin, Claire Mathieu, Neal E. Young

SIAM J. Comput., 2012

Vehicle Scheduling on a Graph Revisited.

Wei Yu, Mordecai J. Golin, Guochuan Zhang

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011

Encoding 2-D Range Maximum Queries

Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, S. Srinivasa Rao

CoRR, 2011

Encoding 2D Range Maximum Queries.

Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, S. Srinivasa Rao

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

2010

A dynamic programming approach to length-limited Huffman coding: space reduction with the Monge property.

Mordecai J. Golin, Yan Zhang

IEEE Trans. Inf. Theory, 2010

The asymptotic number of spanning trees in circulant graphs.

Mordecai J. Golin, Xuerong Yong, Yuanping Zhang

Discret. Math., 2010

2009

The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity.

Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang

ACM Trans. Algorithms, 2009

Online Dynamic Programming Speedups.

Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang

Theory Comput. Syst., 2009

A generic top-down dynamic-programming approach to prefix-free coding.

Mordecai J. Golin, Xiaoming Xu, Jiajin Yu

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Multidimensional Divide-and-Conquer and Weighted Digital Sums.

Yun Kuen Cheung, Philippe Flajolet, Mordecai J. Golin, C. Y. James Lee

Proceedings of the Sixth Workshop on Analytic Algorithmics and Combinatorics, 2009

2008

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding.

Mordecai J. Golin, Jian Li

IEEE Trans. Inf. Theory, 2008

The number of spanning trees in a class of double fixed-step loop networks.

Xuerong Yong, Yuanping Zhang, Mordecai J. Golin

Networks, 2008

A Dynamic Programming Approach To Length-Limited Huffman Coding

Mordecai J. Golin, Yan Zhang

CoRR, 2008

2007

The two-median problem on Manhattan meshes.

Mordecai J. Golin, Yan Zhang

Networks, 2007

Paging Mobile Users Efficiently and Optimally.

Amotz Bar-Noy, Yi Feng, Mordecai J. Golin

Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

2006

Online Maintenance of k-Medians and k-Covers on a Line.

Rudolf Fleischer, Mordecai J. Golin, Yan Zhang

Algorithmica, 2006

Permanents of Circulants: A Transfer Matrix Approach.

Mordecai J. Golin, Yiu-Cho Leung, Yajun Wang

Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005

Chebyshev polynomials and spanning tree formulas for circulant and related graphs.

Yuanping Zhang, Xuerong Yong, Mordecai J. Golin

Discret. Math., 2005

Curve reconstruction from noisy samples.

Siu-Wing Cheng, Stefan Funke, Mordecai J. Golin, Piyush Kumar, Sheung-Hung Poon, Edgar A. Ramos

Comput. Geom., 2005

The Structure of Optimal Prefix-Free Codes in Restricted Languages: The Uniform Probability Case.

Mordecai J. Golin, Zhenming Liu

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Generalizing the Kraft-McMillan Inequality to Restricted Languages.

Mordecai J. Golin, Hyeon-Suk Na

Proceedings of the 2005 Data Compression Conference (DCC 2005), 2005

Counting Structures in Grid Graphs, Cylinders and Tori Using Transfer Matrices: Survey and New Results.

Mordecai J. Golin, Yiu-Cho Leung, Yajun Wang, Xuerong Yong

Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, 2005

2004

Competitive facility location: the Voronoi game.

Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai J. Golin, René van Oostrum

Theor. Comput. Sci., 2004

Finding optimal paths in MREP routing.

Rudolf Fleischer, Mordecai J. Golin, Chin-Tau A. Lea, Steven Wong

Inf. Process. Lett., 2004

New upper and lower bounds on the channel capacity of read/write isolated memory.

Mordecai J. Golin, Xuerong Yong, Yuanping Zhang, Li Sheng

Discret. Appl. Math., 2004

Fun-Sort--or the chaos of unordered binary search.

Therese Biedl, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai J. Golin, James A. King, J. Ian Munro

Discret. Appl. Math., 2004

Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters.

Mordecai J. Golin, Yiu-Cho Leung

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Algorithms for infinite huffman-codes.

Mordecai J. Golin, Kin Keung Ma

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Counting Spanning Trees and Other Structures in Non-constant-jump Circulant Graphs.

Mordecai J. Golin, Yiu-Cho Leung, Yajun Wang

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003

Meeting the Welch and Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets.

Cunsheng Ding, Mordecai J. Golin, Torleiv Kløve

Des. Codes Cryptogr., 2003

On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes.

Mordecai J. Golin, Hyeon-Suk Na

Comput. Geom., 2003

Maximum residual energy routing with reverse energy cost.

Qiling Xie, Chin-Tau A. Lea, Mordecai J. Golin, Rudolf Fleischer

Proceedings of the Global Telecommunications Conference, 2003

Recurrence Relations on Transfer Matrices Yield Good Lower and Upper Bounds on the Channel Capacity of Some 2-Dimensional Constrained Systems (Extended Abstract).

Mordecai J. Golin, Yiu-Cho Leung

Proceedings of the 2003 Data Compression Conference (DCC 2003), 2003

2002

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property.

Phillip G. Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter

J. Algorithms, 2002

Huffman coding with unequal letter costs.

Mordecai J. Golin, Claire Kenyon, Neal E. Young

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The Convex Hull for Random Lines in the Plane.

Mordecai J. Golin, Stefan Langerman, William L. Steiger

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

New Techniques for Bounding the Channel Capacity of Read/Write Isolated Memor.

Xuerong Yong, Mordecai J. Golin

Proceedings of the 2002 Data Compression Conference (DCC 2002), 2002

The probabilistic complexity of the Voronoi diagram of points on a polyhedron.

Mordecai J. Golin, Hyeon-Suk Na

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

2001

A combinatorial approach to Golomb forests.

Mordecai J. Golin

Theor. Comput. Sci., 2001

Lopsided Trees, I: Analyses.

Vicky Siu-Ngan Choi, Mordecai J. Golin

Algorithmica, 2001

Protection of Keys against Modification Attack.

Wai W. Fung, Mordecai J. Golin, James W. Gray III

Proceedings of the 2001 IEEE Symposium on Security and Privacy, 2001

Optimal Prefix-Free Codes That End in a Specified Pattern and Similar Problems: The Uniform Probability Case.

Mordecai J. Golin, Hyeon-Suk Na

Proceedings of the Data Compression Conference, 2001

Competitive Facility Location along a Highway.

Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai J. Golin, René van Oostrum

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000

A dynamic programming algorithm for constructing optimal "1"-ended binary prefix-free codes.

Sze-Lok Chan, Mordecai J. Golin

IEEE Trans. Inf. Theory, 2000

An algorithm for finding a k-median in a directed tree.

Antoine Vigneron, Lixin Gao, Mordecai J. Golin, Giuseppe F. Italiano, Bo Li

Inf. Process. Lett., 2000

The number of spanning trees in circulant graphs.

Yuanping Zhang, Xuerong Yong, Mordecai J. Golin

Discret. Math., 2000

1999

Optimal Point-to-point Broadcast Algorithms Via Lopsided Trees.

Mordecai J. Golin, Assaf Schuster

Discret. Appl. Math., 1999

On the Optimal Placement of Web Proxies in the Internet.

Bo Li, Mordecai J. Golin, Giuseppe F. Italiano, Xin Deng, Kazem Sohraby

Proceedings of the Proceedings IEEE INFOCOM '99, 1999

1998

A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs.

Mordecai J. Golin, Günter Rote

IEEE Trans. Inf. Theory, 1998

Labelled Trees and Pairs of Input-Output Permutations in Priority Queues.

Mordecai J. Golin, Shmuel Zaks

Theor. Comput. Sci., 1998

Randomized Data Structures for the Dynamic Closest-Pair Problem.

Mordecai J. Golin, Rajeev Raman, Christian Schwarz, Michiel H. M. Smid

SIAM J. Comput., 1998

Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems.

Olivier Devillers, Mordecai J. Golin

Int. J. Comput. Geom. Appl., 1998

On the Optimal Placement of Web Proxies in the Internet: The Linear Topology.

Bo Li, Xin Deng, Mordecai J. Golin, Kazem Sohraby

Proceedings of the High Performance Networking, 1998

1996

Prefix Codes: Equiprobable Words, Unequal Letter Costs.

Mordecai J. Golin, Neal E. Young

SIAM J. Comput., 1996

Queries on Voronoi Diagrams of Moving Points.

Olivier Devillers, Mordecai J. Golin, Klara Kedem, Stefan Schirra

Comput. Geom., 1996

Limit Theorems for Minimum-Weight Triangulations, Other Euclidean Functionals, and Probabilistic Recurrence Relations (Extended Abstract).

Mordecai J. Golin

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Lopsided Trees: Analyses, Algorithms, and Applications.

Vicky Siu-Ngan Choi, Mordecai J. Golin

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

Simple Randomized Algorithms for Closest Pair Problems.

Mordecai J. Golin, Rajeev Raman, Christian Schwarz, Michiel H. M. Smid

Nord. J. Comput., 1995

Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas.

Olivier Devillers, Mordecai J. Golin

Inf. Process. Lett., 1995

A Dynamic Programming Algorithm for Constructing Optimal Refix-Free Codes for Unequal Letter Costs.

Mordecai J. Golin, Günter Rote

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

The Multi-Weighted Spanning Tree Problem (Extended Abstract).

Joseph L. Ganley, Mordecai J. Golin, Jeffrey S. Salowe

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994

Newton's Method for Quadratics, and Nested Intervals.

Mordecai J. Golin, Kenneth J. Supowit

Complex Syst., 1994

A Provably Fast Linear-Expected-Time Maxima-Finding Algorithm.

Mordecai J. Golin

Algorithmica, 1994

Mellin Transforms and Asymptotics: The Mergesort Recurrence.

Philippe Flajolet, Mordecai J. Golin

Acta Informatica, 1994

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points.

Olivier Devillers, Mordecai J. Golin, Klara Kedem, Stefan Schirra

Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993

Queue-Mergesort.

Mordecai J. Golin, Robert Sedgewick

Inf. Process. Lett., 1993

Maxima in Convex Regions.

Mordecai J. Golin

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Exact Asymptotics of Divide-and-Conquer Recurrences.

Philippe Flajolet, Mordecai J. Golin

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

1992

How Many Maxima Can There Be?

Mordecai J. Golin

Comput. Geom., 1992

Dynamic Closest Pairs - A Probabilistic Approach.

Mordecai J. Golin

Proceedings of the Algorithm Theory, 1992

1988

Analysis of a Simple Yet Efficient Convex Hull Algorithm.

Mordecai J. Golin, Robert Sedgewick

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988