Timothy M. Chan, Alexander Golynski, Alejandro López-ortiz, Claude-guy Quimper
We consider two variants of the well-known “sailor in the fog ” puzzle. The first version (the “asteroid surveying” problem) is set in three dimensions and asks for the shortest curve that...
A note on the power of quantum fingerprinting (2005)
Golynski, Alexander, Sen, Pranab
In this short note, we improve and extend Yao's paper "On the power of quantum fingerprinting" about simulating a classical public coin simultaneous message protocol by a quantum simultaneous message...
Improved algorithms for the global cardinality constraint (2004)
Claude-guy Quimper, Peter Van Beek, Alexander Golynski
Abstract. We study the global cardinality constraint (gcc) and propose an O(n
Improved algorithms for the global cardinality constraint (2004)
Claude-guy Quimper, Ro López-ortiz, Peter Van Beek, Alexander Golynski
Abstract. We study the global cardinality constraint (gcc) and propose an O(n 1.5 d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency, where n is the number of...
Curves of width one and the river shore problem (2003)
Timothy M. Chan, Alexander Golynski
We consider the problem of nding the shortest curve in the plane that has unit width. This problem was rst posed as the \river shore " puzzle by Ogilvy (1972) and is related to the area of...
The Asteroid Surveying Problem and Other Puzzles (2003)
Timothy M. Chan, Alexander Golynski, Alejandro Lopez-Ortiz, Claude-Guy Quimper
We consider two variants of the well-known "sailor in the fog" puzzle. The first version (the "asteroid surveying" problem) is set in three dimensions and asks for the shortest...
An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint (2003)
Claude-guy Quimper, Peter Van Beek, Alejandro Lopez-Ortiz, Alexander Golynski, Ro Lopez-ortiz, Er Golynski, ...
Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the e#ciency of a constraint programming approach. In this paper we present an...
Sufficiently Fat Polyhedra are not 2-castable (2002)
Bremner, David, Golynski, Alexander
In this note we consider the problem of manufacturing a convex polyhedral object via casting. We consider a generalization of the sand casting process where the object is manufactured by gluing...
A polynomial time algorithm to find the minimum cycle basis of a regular matroid. (2002)
The Minimum Cycle Basis Problem (MCBP) is: given a binary matroid with positive weights assigned to its elements, what is the set of circuits with total smallest weight which generate all of the...