Source author record

Yingli Ran

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 Computational Geometry Discrete Mathematics math.CO

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A parallel algorithm for minimum weight set cover with small neighborhood property

This paper studies the minimum weight set cover (MinWSC) problem with a {\em small neighborhood cover} (SNC) property proposed by Agarwal {\it et al.} in \cite{Agarwal.}. A parallel algorithm for MinWSC with $τ$ -SNC property is presented, obtaining approximation ratio $τ(1+3\varepsilon)$ in $O(L\log_{1+\varepsilon}\frac{n^3}{\varepsilon^2}+ 4τ^{3}2^τL^2\log n)$ rounds, where $0< \varepsilon <\frac{1}{2}$ is a constant, $n$ is the number of elements, and $L$ is a parameter related to SNC property. Our results not only improve the approximation ratio obtained in \cite{Agarwal.}, but also answer two questions proposed in \cite{Agarwal.}.

preprint2022arXiv

Approximation Algorithm for Minimum $p$ Union Under a Geometric Setting

In a minimum $p$ union problem (Min $p$ U), given a hypergraph $G=(V,E)$ and an integer $p$ , the goal is to find a set of $p$ hyperedges $E'\subseteq E$ such that the number of vertices covered by $E'$ (that is $|\bigcup_{e\in E'}e|$ ) is minimized. It was known that Min $p$ U is at least as hard as the densest $k$ -subgraph problem. A question is: how about the problem in some geometric settings? In this paper, we consider the unit square Min $p$ U problem (Min $p$ U-US) in which $V$ is a set of points on the plane, and each hyperedge of $E$ consists of a set of points in a unit square. A $(\frac{1}{1+\varepsilon},4)$ -bicriteria approximation algorithm is presented, that is, the algorithm finds at least $\frac{p}{1+\varepsilon}$ unit squares covering at most $4opt$ points, where $opt$ is the optimal value for the Min $p$ U-US instance (the minimum number of points that can be covered by $p$ unit squares).

preprint2022arXiv

Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function $f\colon 2^V \rightarrow \mathbb{Z}^+$ , a linear cost function $c: V\rightarrow \mathbb R^{+}$ , and an integer $k\leq f(V)$ , the goal is to find a subset $A\subseteq V$ with the minimum cost such that $f(A)\geq k$ . The MinSMC can be found at the heart of many machine learning and data mining applications. In this paper, we design a parallel algorithm for the MinSMC that takes at most $O(\frac{\log km\log k(\log m+\log\log mk)}{\varepsilon^4})$ adaptive rounds, and it achieves an approximation ratio of $\frac{H(\min\{Δ,k\})}{1-5\varepsilon}$ with probability at least $1-3\varepsilon$ , where $Δ=\max_{v\in V}f(v)$ , $H(\cdot)$ is the Harmonic number, $m=|V|$ , and $\varepsilon$ is a constant in $(0,\frac{1}{5})$ .

preprint2022arXiv

Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set

A connected dominating set is a widely adopted model for the virtual backbone of a wireless sensor network. In this paper, we design an evolutionary algorithm for the minimum connected dominating set problem (MinCDS), whose performance is theoretically guaranteed in terms of both computation time and approximation ratio. Given a connected graph $G=(V,E)$ , a connected dominating set (CDS) is a subset $C\subseteq V$ such that every vertex in $V\setminus C$ has a neighbor in $C$ , and the subgraph of $G$ induced by $C$ is connected. The goal of MinCDS is to find a CDS of $G$ with the minimum cardinality. We show that our evolutionary algorithm can find a CDS in expected $O(n^3)$ time which approximates the optimal value within factor $(2+\lnΔ)$ , where $n$ and $Δ$ are the number of vertices and the maximum degree of graph $G$ , respectively.

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.

Yingli Ran

Research overview

Is this your work?

4 publications

A parallel algorithm for minimum weight set cover with small neighborhood property

Approximation Algorithm for Minimum $p$ Union Under a Geometric Setting

Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set

See the researcher in context

Building this map preview

Yingli Ran

Research overview

Is this your work?

4 publications

A parallel algorithm for minimum weight set cover with small neighborhood property

Approximation Algorithm for Minimum ppp Union Under a Geometric Setting

Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set

See the researcher in context

Building this map preview

Approximation Algorithm for Minimum $p$ Union Under a Geometric Setting