Source author record

Ching-Lueh Chang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computational Complexity Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

6works

4topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

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

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 \mathbb{Z}^+\to\mathbb{Z}^+$ satisfying $f(n)=ω(1)$ , {\sc metric $1$ -median} has a deterministic, $o(n)$ -query, $o(f(n)\cdot\log n)$ -approximation and nonadaptive algorithm. Previously, no deterministic $o(n)$ -query $o(n)$ -approximation algorithms are known for {\sc metric $1$ -median}. On the negative side, we prove each deterministic $O(n)$ -query algorithm for {\sc metric $1$ -median} to be not $(δ\log n)$ -approximate for a sufficiently small constant $δ>0$ . We also refute the existence of deterministic $o(n)$ -query $O(\log n)$ -approximation algorithms.

preprint2015arXiv

A deterministic sublinear-time nonadaptive algorithm for metric $1$ -median selection

We give a deterministic $O(hn^{1+1/h})$ -time $(2h)$ -approximation nonadaptive algorithm for $1$ -median selection in $n$ -point metric spaces, where $h\in\mathbb{Z}^+\setminus\{1\}$ is arbitrary. Our proof generalizes that of Chang.

preprint2015arXiv

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

Consider the problem of finding a point in a metric space $(\{1,2,\ldots,n\},d)$ with the minimum average distance to other points. We show that this problem has no deterministic $o(n^{1+1/(h-1)})$ -query $(2h-Ω(1))$ -approximation algorithms for any constant $h\in\mathbb{Z}^+\setminus\{1\}$ .

preprint2014arXiv

A lower bound for metric 1-median selection

Consider the problem of finding a point in an n-point metric space with the minimum average distance to all points. We show that this problem has no deterministic $o(n^2)$ -query $(4-Ω(1))$ -approximation algorithms.

preprint2010arXiv

On irreversible dynamic monopolies in general graphs

Consider the following coloring process in a simple directed graph $G(V,E)$ with positive indegrees. Initially, a set $S$ of vertices are white, whereas all the others are black. Thereafter, a black vertex is colored white whenever more than half of its in-neighbors are white. The coloring process ends when no additional vertices can be colored white. If all vertices end up white, we call $S$ an irreversible dynamic monopoly (or dynamo for short) under the strict-majority scenario. An irreversible dynamo under the simple-majority scenario is defined similarly except that a black vertex is colored white when at least half of its in-neighbors are white. We derive upper bounds of $(2/3)\,|\,V\,|$ and $|\,V\,|/2$ on the minimum sizes of irreversible dynamos under the strict and the simple-majority scenarios, respectively. For the special case when $G$ is an undirected connected graph, we prove the existence of an irreversible dynamo with size at most $\lceil |\,V\,|/2 \rceil$ under the strict-majority scenario. Let $ε>0$ be any constant. We also show that, unless $\text{NP}\subseteq \text{TIME}(n^{O(\ln \ln n)}),$ no polynomial-time, $((1/2-ε)\ln |\,V\,|)$ -approximation algorithms exist for finding the minimum irreversible dynamo under either the strict or the simple-majority scenario. The inapproximability results hold even for bipartite graphs with diameter at most 8.

preprint2010arXiv

On reversible cascades in scale-free and Erdős-Rényi random graphs

Consider the following cascading process on a simple undirected graph $G(V,E)$ with diameter $Δ$ . In round zero, a set $S\subseteq V$ of vertices, called the seeds, are active. In round $i+1,$ $i\in\mathbb{N},$ a non-isolated vertex is activated if at least a $ρ\in(\,0,1\,]$ fraction of its neighbors are active in round $i$ ; it is deactivated otherwise. For $k\in\mathbb{N},$ let $\text{min-seed}^{(k)}(G,ρ)$ be the minimum number of seeds needed to activate all vertices in or before round $k$ . This paper derives upper bounds on $\text{min-seed}^{(k)}(G,ρ)$ . In particular, if $G$ is connected and there exist constants $C>0$ and $γ>2$ such that the fraction of degree- $k$ vertices in $G$ is at most $C/k^γ$ for all $k\in\mathbb{Z}^+,$ then $\text{min-seed}^{(Δ)}(G,ρ)=O(\lceilρ^{γ-1}\,|\,V\,|\rceil)$ . Furthermore, for $n\in\mathbb{Z}^+,$ $p=Ω((\ln{(e/ρ)})/(ρn))$ and with probability $1-\exp{(-n^{Ω(1)})}$ over the Erdős-Rényi random graphs $G(n,p),$ $\text{min-seed}^{(1)}(G(n,p),ρ)=O(ρn)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ching-Lueh Chang

Research overview

Is this your work?

6 publications

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

A deterministic sublinear-time nonadaptive algorithm for metric $1$ -median selection

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

A lower bound for metric 1-median selection

On irreversible dynamic monopolies in general graphs

On reversible cascades in scale-free and Erdős-Rényi random graphs

See the researcher in context

Building this map preview

Ching-Lueh Chang

Research overview

Is this your work?

6 publications

Deterministic metric 111-median selection with very few queries

A deterministic sublinear-time nonadaptive algorithm for metric 111-median selection

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

A lower bound for metric 1-median selection

On irreversible dynamic monopolies in general graphs

On reversible cascades in scale-free and Erdős-Rényi random graphs

See the researcher in context

Building this map preview

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

A deterministic sublinear-time nonadaptive algorithm for metric $1$ -median selection

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