Online Dynamic Programming Speedups ∗ (2009)
Amotz Bar-noy, Mordecai J. Golin, Yan Zhang
Consider the dynamic program h(n) = min1≤j≤n a(n, j), where a(n, j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i < n. The goal is to...
Permanents of Circulants: a Transfer Matrix Approach ∗ (Extended Abstract) (2009)
Mordecai J. Golin, Yiu Cho, Leung Yajun Wang
Calculating the permanent of a (0,1) matrix is a #P-complete problem but there are some classes of structured matrices for which the permanent is calculable in polynomial time. The most well-known...
The Two-Median Problem on Manhattan Meshes (2009)
We investigate the two-median problem on a mesh with M columns and N rows (M ≥ N), under the Manhattan (L1) metric. We derive exact algorithms with respect to m, n, and r, the number of columns,...
Mordecai J. Golin, Yiu Cho, Leung Yajun, Wang Xuerong Yong
There is a very large literature devoted to counting structures, e.g., spanning trees, Hamiltonian cycles, independent sets, acyclic orientations, in the n × m grid graph G(n, m). In particular the...
Permanents of Circulants: a Transfer Matrix Approach (Extended Abstract) (2008)
Mordecai J. Golin, Yiu Cho Leung, Yajun Wang
Calculating the permanent of a (0,1) matrix is a #P-complete problem but there are some classes of structured matrices for which the permanent is calculable in polynomial time. The most well-known...
Mordecai J. Golin, Zhenming Liu
(Extended Abstract) ⋆
It will not discuss many other important generalizations, e.g.,
Mordecai J. Golin, Zhenming Liu
Abstract. In this paper we discuss the problem of constructing minimum-cost, prefix-free codes for equiprobable words under the assumption that all codewords are restricted to belonging to an...
Rudolf Fleischer, Mordecai J. Golin, Zhang Yan
Abstract. The standard dynamic programming solution to finding kmedians on a line with n nodes requires O(kn 2) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality...
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n pointscanbeasbadasΘ(n 2). Interest has recently arisen as to what...
Online Dynamic Programming Speedups ⋆ (2008)
Amotz Bar-noy, Mordecai J. Golin, Yan Zhang
Abstract. Consider the Dynamic Program h(n) = min1≤j≤n a(n, j) for n =1, 2,...,N. For arbitrary values of a(n, j), calculating all the h(n) requires Θ(N 2) time. It is well known that, if the...
Extended Abstract, Mordecai J. Golin
Let MWT(n) be the weight of a minimum-weight triangu-lation of n points chosen independently from the uniform distribution over [0, 112. Previous work [ll] has shown that E(MWT(n)) = e(&). In...
Abstract Algorithms for Infinite Huffman-Codes ∗ (Extended Abstract) (2008)
Mordecai J. Golin, Kin Keung Ma
Optimal (minimum cost) binary prefix-free codes for infinite sources with geometrically distributed frequencies, e.g., P = {pi (1 − p)} ∞ i=0, 0 < p < 1, were first (implicitly) suggested...
Rudolf Fleischer, Mordecai J. Golin, Zhang Yan
Abstract. The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn 2) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality...
HKUST Theoretical Computer Science (2007)
Yuanping Zhang, Mordecai J. Golin, Clear Water Bay
Chebyshev polynomials and spanning tree formulas for circulant and related graphs
n log n) time, in a random tree O(k (2007)
Antoine Vigneron, Lixin Gao, Mordecai J. Golin, Bo Li
We consider the problem of finding a k-median in a directed tree. We present an algorithm that computes a k-median in O(Pk 2) time where k is the number of resources to be placed and P is the path...
Mordecai J. Golin, Mordecai J. Golin, Günter Rote, Günter Rote, ...
We consider the problem of constructing prefix-free codes of minimum cost when the encoding alphabet contains letters of unequal length. The complexity of this problem has been unclear for thirty...
Gfnter Rote, Mordecai J. Golin, Mordecai J. Golin
und KONTROLLE
Mordecai J. Golin, Claire Kenyon, Neal E. Young
In the standard Human coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must...
Mordecai J. Golin, Xuerong Yong, Yuanping Zhang
Let T(G) be the number of spanning trees in graph G. In this note we explore the asymptotics of T(G) for circulant graphs. The circulant graph C s1,s2,···,sk
The Asymptotic Number of Spanning Trees in Circulant Graphs (Extended Abstract) ∗ (2006)
Mordecai J. Golin, Xuerong Yong, Yuanping Zhang
Let T(G) be the number of spanning trees in graph G. In this note we explore the asymptotics of T(G) for circulant graphs. The circulant graph Cs1,s2,···,sk n is the 2k regular graph with n...
Mordecai J. Golin, Yiu Cho Leung
Abstract It has long been known that the number of spanning trees in n node circulant graphs with fixed jumps satisfies a bounded order, constant coefficient, recurrence relation in n. The proof of...
Online Maintenance of KMedians and K-Covers on a Line (2004)
Rudolf Fleischer, Mordecai J. Golin, Yan Zhang
The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn 2) time. Dynamic programming speedup techniques, e.g., use of the quadrangle inequality or...
Counting spanning trees and other structures in non constant-jump circulant graphs (2004)
Mordecai J. Golin, Yiu Cho Leung, Yajun Wang
Abstract. Circulant graphs are an extremely well-studied subclass of regular graphs, partially because they model many practical computer network topologies. It has long been known that the number of...
Online Maintenance of KMedians and K-Covers on a Line (2004)
Rudolf Fleischer, Mordecai J. Golin, Yan Zhang
The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn 2) time. Dynamic programming speedup techniques, e.g., use of the quadrangle inequality or...
Mordecai J. Golin, Yiu Cho Leung
Abstract. It has long been known that the number of spanning trees in circulant graphs with fixed jumps and n nodes satisfies a recurrence relation in n. The proof of this fact was algebraic...
Algorithms for infinite Huffman-codes (2003)
Golin, Mordecai J., Ma, Kin Keung
Optimal (minimum cost) binary prefix-free codes for infinite sources with geometrically distributed frequencies, e.g., P = {pi(1 - p)}∞i=0, 0 < p < 1, were first (implicitly) suggested by Golomb...
Maximum residual energy routing with reverse energy cost (2003)
Xie, Qiling, Lea, Chin-Tau, Golin, Mordecai J., Fleischer, Rudolf H.
The Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in a battery wireless network. Past studies on MREP are based on the assumption that...
Finding optimal paths in MREP routing (2003)
Fleischer, Rudolf H., Golin, Mordecai J., Lea, Chin-Tau, Wong, Steven
Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the...
Curve reconstruction from noisy samples (2003)
Cheng, Siu-Wing, Funke, Stefan, Golin, Mordecai J., Kumar, Piyush, Poon, Sheung-Hung, Ramos, Edgar A.
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Curve Reconstruction from Noisy Samples (2003)
Cheng,Siu-Wing, Funke,Stefan, Golin,Mordecai J., Kumar,Piyush, Poon,Sheung-Hung, Ramos,Edgar A.
Curve Reconstruction from Noisy Samples (2003)
Cheng, Siu-Wing, Funke, Stefan, Golin, Mordecai J., Kumar, Piyush, Poon, Sheung-Hung, Ramos, Edgar A.
Maximum residual energy routing with reverse energy cost (2003)
Qiling Xie, Chin-tau Lea, Mordecai J. Golin, Rudolf Fleischer
Abstract-The Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in a battery wireless network. Past studies on MREP are based on the...
The Convex hull for random lines in the plane (2002)
Golin, Mordecai J., Langerman, Stefan, Steiger, William
An arrangement of n lines chosen at random from R2 has a vertex set whose convex hull has constant (expected) size.
Chebyshev polynomials and spanning tree formulas for circulant and related graphs (2002)
Zhang, Yuanping, Golin, Mordecai J.
Kirchhoff's Matrix Tree Theorem permits the calculation of the number of spanning trees in any given graph G through the evaluation of the determinant of an associated matrix. In the case of some...
Meeting the Welch and Karystinos-Pados bounds on DS-CDMA binary signature sets (2002)
Ding, Cunsheng, Golin, Mordecai J., KlΦve, Torleiv
The Welch lower bound on the total-squared-correlation (TSC) of binary signature sets is loose for binary signature sets whose length L is not a multiple of 4. Recently Karystinos and Pados developed...
Huffman coding with unequal letter costs (2002)
Golin, Mordecai J., Kenyon, Claire, Young, Neal E.
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
Huffman coding with unequal letter costs (2002)
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
Huffman coding with unequal letter costs (2002)
Mordecai J. Golin, Claire Kenyon, Neal E. Young
In the standard Hu#man coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding...
The probabilistic complexity of the Voronoi diagram of points on a polyhedron (2001)
Na, Hyeon-Suk, Golin, Mordecai J.
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n2). Interest has recently arisen as to what...
Golin, Mordecai J., Na, Hyeon-Suk
Let P be the boundary of a convex polytope and Sn be a set of points drawn from the 2-dimensional Poisson distribution with rate n over P. In a companion paper [1] the authors show that the expected...
Biedl, Therese, Chan, Timothy, Demaine, Erik D., Fleischer, Rudolf H., Golin, Mordecai J., Munro, J. Ian
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements...
Protection of keys against modification attack (2001)
Fung, Wai W., Golin, Mordecai J.
In recent work, Anderson and Kuhn [3] described an attack against tamper-resistant devices wherein a secret key stored in EEPROM is compromised using a simple and lowcost attack. The attack consists...
On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes (2001)
Golin, Mordecai J., Na, Hyeon-Suk
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as ⊝(n2). It is also known that if the points are...
Competitive facility location along a highway (2001)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Golin, Mordecai J., Van Oostrum, Rene
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Competitive facility location : the Voronoi game (2001)
Ahn, Hee-Kap, Cheng, Siu-Wing, Cheong, Otfried, Golin, Mordecai J., Van Oostrum, Rene
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is...
Protection of Keys against Modification Attack (2001)
Wai W. Fung, Mordecai J. Golin, James W. Gray
In recent work, Anderson and Kuhn [3] described an attack against tamper-resistant devices wherein a secret key stored in EEPROM is compromised using a simple and lowcost attack. The attack consists...
The Probabilistic Complexity of the Voronoi Diagram of Points on (2001)
Theoretical Computer Science, A Polyhedron, Mordecai J. Golin, Hyeon-suk Na
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3dimensional Voronoi diagram of n points can be as bad as \Theta(n ): Interest has recently arisen as to...
Lopsided trees : analyses, algorithms, and applications (2000)
Choi, Vicky, Golin, Mordecai J.
Lopsided trees are rooted, ordered, trees in which the length of an edge from a node to its ith child depends upon the value of i. These trees model a variety of problems and have therefore been...
New upper and lower bounds on the channel capacity of read/write isolated memory (2000)
Golin, Mordecai J., Yong, Xuerong, Zhang, Yuanping, Sheng, Li
In this paper we refine upper and lower bounds for the channel capacity of a serial, binary rewritable medium in which no consecutive locations may store '1's and no consecutive locations may be...
An Algorithm for finding a k-median in a directed tree (2000)
Vigneron, Antoine, Gao, Lixin, Golin, Mordecai J., Italiano, Giuseppe F., Li, Bo
We consider the problem of finding a k-median in a directed tree. We present an algorithm that computes a k-median in O(Pk2) time where k is the number of resources to be placed and P is the path...
Bradford, Phil, Golin, Mordecai J., Larmore, Lawrence L., Rytter, Wojciech
In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost...
An algorithm for finding a k-median in a directed tree (2000)
Antoine Vigneron, Lixin Gao, Mordecai J. Golin
We consider the problem of finding a k-median in a directed tree. We present an algorithm that computes a k-median in O(P k 2) time where k is the number of resources to be placed and P is the path...
A dynamic programming algorithm for constructing optimal “1”-ended binary prefix-free codes (2000)
Sze-lok Chan, Mordecai J. Golin
[9] , “Coding for a binary independent piecewise-identically-distributed-source,”
On the optimal placement of web proxies in the internet: the linear topology (1999)
Li, Bo, Deng, Xin, Golin, Mordecai J., Sohraby, Kazem
Web caching or web proxy has been considered as the prime vehicle to cope with the ever-increasing demand for information retrieval over the Internet, WWW being a typical example. The existing work...
The Number of spanning trees in circulant graphs (1999)
Zhang, Yuanping, Yong, Xuerong, Golin, Mordecai J.
In this paper we develop a method for determining the exact number of spanning trees in (directed or undirected) circulant graphs. Using this method we can, for any class of circulant graph, exhibit...
THE NUMBER OF SPANNING TREES IN CIRCULANT GRAPHS\Lambda (1999)
Yuanping Zhangy, Xuerong Yongz, Mordecai J. Golin
Abstract In this paper we develop a method for determining the exact number of spanning trees in (directed or undirected) circulant graphs. Using this method we can, for any class of circulant graph,...
On the expected depth of random circuits (1999)
Sunil Arya, Mordecai J. Golin, Kurt Mehlhorn
Abstract: In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from...
On the Expected Depth of Random Circuits (1999)
Arya, Sunil, Golin, Mordecai J., Mehlhorn, Kurt
In this paper we analyse the expected depth of random circuits of fixed fanin f . Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
Dynamic and distributed web caching in active networks (1998)
Li, Bo, Deng, Xin, Golin, Mordecai J., Sohraby, Kazem
Web caching or web proxy has been considered as the prime vehicle of coping with the ever-increasing demand for information retrieval over wide-area networks, WWW being a typical example. Existing...
Randomized data structures for the dynamic closest-pair problem (1998)
Golin, Mordecai J., Raman, Rajeev, Schwarz, Christian, Smid, Michiel
We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional...
On the expected depth of random circuits (1998)
Arya, Sunil, Golin, Mordecai J., Mehlhorn, Kurt
In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
Günter Rote, Mordecai J. Golin
We consider the problem of constructing prefix-free codes of minimum cost when the encoding alphabet contains letters of unequal length. The complexity of this problem has been unclear for...
Phil Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter
The Monge property emerges, sometimes quite mysteriously, in many optimization problems and usually leads to running time improvements of at least a linear factor. In this paper a novel application...
Phil Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter
In this paper we discuss a variation of the classical Huffman coding problem: finding optimal prefix-free codes for unequal letter costs. Our problem consists of finding a minimal cost prefix-free...
On the Expected Depth of Random Circuits (1998)
Sunil Arya, Mordecai J. Golin, Kurt Mehlhorn
: In this paper we analyze the expected depth of random circuits of fixed fanin f: Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
Prefix codes: Equiprobable words, unequal letter costs (1996)
Abstract. We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities ofthe words, are nonuniform: "Given an alphabet of r letters of...
Lopsided trees: analyses, algorithms, and applications (1996)
Lopsided trees are rooted, ordered, trees in which the length of an edge from a node to its i th child depends upon the value of i: These trees model a variety of problems and have therefore been...
Prefix codes: Equiprobable words, unequal letter costs (1996)
Abstract. We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are non-uniform: "Given an alphabet of r letters...
Olivier Devillers, Mordecai J. Golin
Abstract: The existing O(n log n) algo rithms for nding the convex hulls of circles and the lower envelope of parabolas follow the di vide-and-conquer paradigm. The diOEculty with developing...
Mellin transforms and asymptotics : the mergesort recurrence (1993)
Flajolet, Philippe, Golin, Mordecai J.
Mellin transforms and Dirichlet series are useful in quantifying periodicity phenomena present in recursive divide-and-conquer algorithms. This note illustrates the techniques by providing a precise...