Timothy M. Chan's Publications: Miscellaneous topics

More on change-making and related problems

Qizheng He)

Given a set of n integer-valued coin types and a target value t, the well-known change-making problem asks for the minimum number of coins that sum to t, assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j, for every j=0,...,t. For example, the textbook dynamic programming algorithms can solve the all-targets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version.

In this paper, we obtain a number of new results on change-making and related problems:

  1. We present a new algorithm for the all-targets change-making problem with running time O~(t^{4/3}), improving a previous O~(t^{3/2})-time algorithm.
  2. We present a very simple O~(u^2 + t)-time algorithm for the all-targets change-making problem, where u denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erdös and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by u).
  3. For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He's algorithms that runs in O~(u) time (instead of O~(t)).
  4. For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in O~(nu) time, improving previous near-u^2-time algorithms.
  5. We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case).

On the change-making problem

(with Qizheng He)

Given a set of n non-negative integers representing a coin system, the change-making problem seeks the fewest number of coins that sum up to a given value t, where each type of coin can be used an unlimited number of times. This problem is a popular homework exercise in dynamic programming, where the textbook solution runs in O(nt) time.

It is not hard to solve this problem in O(t polylog t) time by using convolution. In this paper, we present a simple deterministic O(t log t loglog t) time algorithm, and later improve the running time to O(t log t) by randomization.

An improved approximation algorithms for the discrete Fr�chet distance

Zahed Rahmati)

For two sequences P and Q of n points in R^d, we compute an approximation to the discrete Fr�chet distance. Our f-approximation algorithm runs in time O(n logn +n^2/f^2), for any f in [1, n/logn] and d=O(1), which improves (and, at the same time, slightly simplifies) the previous O(n logn +n^2/f)-time algorithm by Bringmann and Mulzer [SoCG�15].

Approximation schemes for 0-1 knapsack

We revisit the standard 0-1 knapsack problem. The latest polynomial-time approximation scheme by Rhee (2015) with approximation factor 1+epsilon has running time near O~(n+(1/epsilon)^{5/2}) (ignoring polylogarithmic factors), and is randomized. We present a simpler algorithm which achieves the same result and is deterministic.

With more effort, our ideas can actually lead to an improved time bound near O~(n + (1/epsilon)^{12/5}), and still further improvement for small n.

Speeding up the Four Russians algorithm by about one more logarithmic factor

We present a new combinatorial algorithm for Boolean matrix multiplication that runs in O(n^3 (loglog n)^3 / log^3 n) time. This improves the previous combinatorial algorithm by Bansal and Williams [FOCS'09] that runs in O(n^3 (loglog n)^2 / log^{9/4} n) time. Whereas Bansal and Williams' algorithm uses regularity lemmas for graphs, the new algorithm is simple and uses entirely elementary techniques: table lookup, word operations, plus a deceptively straightforward divide-and-conquer.

Our algorithm is in part inspired by a recent result of Impagliazzo, Lovett, Paturi, and Schneider (2014) on a different geometric problem, offline dominance range reporting; we improve their analysis for that problem as well.

Succinct indices for path minimum with applications to path reporting

Meng He, J. Ian Munro, and Gelin Zhou)

In the path minimum query problem, we preprocess a tree on n weighted nodes, such that given an arbitrary path, we can locate the node with the smallest weight along this path. We design novel succinct indices for this problem; one of our index structures supports queries in O(alpha(m,n)) time, and occupies O(m) bits of space in addition to the space required for the input tree, where m is an integer greater than or equal to n and alpha(m,n) is the inverse-Ackermann function. These indices give us the first succinct data structures for the path minimum problem, and allow us to obtain new data structures for path reporting queries, which report the nodes along a query path whose weights are within a query range. We achieve three different time/space tradeoffs for path reporting by designing (a) an O(n)-word structure with O(lg^eps n + occ lg^eps n) query time, where occ is the number of nodes reported; (b) an O(n lglg n)-word structure with O(lglg n + occ lglg n) query time; and (c) an O(n lg^eps n)- word structure with O(lglg n + occ) query time. These tradeoffs match the state of the art of two-dimensional orthogonal range reporting queries which can be treated as a special case of path reporting queries. When the number of distinct weights is much smaller than n, we further improve both the query time and the space cost of these three results.

A randomized algorithm for online unit clustering

Hamid Zarrabi-Zadeh)

In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naive upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to two dimensions.

Finding the shortest bottleneck edge in a parametric minimum spanning tree

Given a parametric graph with n vertices and m edges where edge weights change linearly over time, we show how to find the time value at which the heaviest edge weight in the minimum spanning tree is minimized in O(n(m/n)^epsilon log n + m) expected time...

Balanced k-colorings

Therese C. Biedl, Eowyn Cenek, Erik D. Demaine, Martin Demaine, Rudolf Fleischer, and Ming-Wei Wang)

While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k>=2, a set of vertices to minimize imbalance among a family of subsets of vertices. The imbalance is the maximum, over all subsets in the family, of the largest difference between the size of any two color classes in that subset. The discrepancy is the minimum possible imbalance. We show that the discrepancy is always at most 4d-3, where d (the "dimension") is the maximum number of subsets containing a common vertex. For 2-colorings, the bound on the discrepancy is at most max{2d-3, 2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.

Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees

This note gives a short proof of a sampling lemma used by Karger, Klein, and Tarjan in the analysis of their randomized linear-time algorithm for minimum spanning trees.

Copyright Notice

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Timothy Chan (Last updated Aug 2023)