Ching-Lueh Chang

activity

20072022

most citedOn irreversible dynamic monopolies in general graphs

17 citations · 25 across the 11 of their papers we have counts for

collaborators

11 papers

cs.DS2022

Deterministic metric $1$ -median selection with very few queries

Ching-Lueh Chang

Given an $n$ -point metric space $(M, d)$ , {\sc metric $1$ -median} asks for a point $p \in M$ minimizing $\sum_{x \in M} d (p, x)$ . We show that for each computable function $f\colon \m…

cs.DS2019

On ultrametric $1$ -median selection

Ching-Lueh Chang

Consider the problem of finding a point in an ultrametric space with the minimum average distance to all points. We give this problem a Monte Carlo $O ((lo g^{2} (1/ ε)) / ε^{3})$ -time $(1+…

cs.DS2017

Metric random matchings with applications

Ching-Lueh Chang

Let $({1, 2, \dots, n}, d)$ be a metric space. We analyze the expected value and the variance of $\sum_{i = 1}^{⌊ n /2 ⌋} d (π (2 i - 1), π (2 i))$ for a…

cs.DS2017

A Las Vegas approximation algorithm for metric $1$ -median selection

Ching-Lueh Chang

Given an $n$ -point metric space, consider the problem of finding a point with the minimum sum of distances to all points. We show that this problem has a randomized algorithm that…

cs.DS2016

Metric 1-median selection with fewer queries

Ching-Lueh Chang

Let $h : Z^{+} \to Z^{+} ∖ {1}$ be any function such that $h (n)$ and $⌈ n^{1/ h (n)} ⌉$ are computable from $n$ in $O (h (n) \cdot n^{1 + 1/ h (n)})$ time. W…

cs.CC2015

Metric $1$ -median selection: Query complexity vs. approximation ratio

Ching-Lueh Chang

Consider the problem of finding a point in a metric space $({1, 2, \dots, n}, d)$ with the minimum average distance to other points. We show that this problem has no deterministic $…

Deterministic metric 1-median selection with very few queries

On ultrametric 1-median selection

Metric random matchings with applications

A Las Vegas approximation algorithm for metric 1-median selection

Metric 1-median selection with fewer queries

Metric 1-median selection: Query complexity vs. approximation ratio

Deterministic metric $1$ -median selection with very few queries

On ultrametric $1$ -median selection

A Las Vegas approximation algorithm for metric $1$ -median selection

Metric $1$ -median selection: Query complexity vs. approximation ratio