Arrow Research search

Author name cluster

Lidong Wu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
1 author row

Possible papers

6

TCS Journal 2021 Journal Article

Approximation algorithms for the submodular edge cover problem with submodular penalties

  • Xin Wang
  • Suogang Gao
  • Bo Hou
  • Lidong Wu
  • Wen Liu

In this paper, we consider the submodular edge cover problem with submodular penalties. In this problem, we are given an undirected graph G = ( V, E ) with vertex set V and edge set E. Assume the covering cost function c: 2 E → R + and the penalty function p: 2 V → R + are both submodular with p non-decreasing, c ( ∅ ) = 0 and p ( ∅ ) = 0. The goal of the submodular edge cover problem with submodular penalties is to select an edge subset to cover some vertices and penalize the vertex subset containing uncovered vertices such that the total cost of covering and penalty is minimized. For this problem, we first give a 2Δ-approximation algorithm by using a primal-dual technique, where Δ is the maximal degree of the graph G. Then we transform this problem into a submodular set cover problem, and by applying a known result for the submodular set cover problem we conclude that there is an approximation algorithm with an approximation ratio Δ + 1.

Details DOI

TCS Journal 2021 Journal Article

On approximation algorithm for the edge metric dimension problem

  • Yufei Huang
  • Bo Hou
  • Wen Liu
  • Lidong Wu
  • Stephen Rainwater
  • Suogang Gao

In this paper, we study the edge metric dimension problem (EMDP). We establish a potential function and give a corresponding greedy algorithm with approximation ratio 1 + ln ⁡ n + ln ⁡ ( log 2 ⁡ n ), where n is the number of vertices in the graph G.

Details DOI

TCS Journal 2021 Journal Article

On continuous one-way functions

  • Ker-I Ko
  • Lidong Wu

The existence of one-way functions seems to depend, intuitively, on certain irregular properties of polynomial-time computable functions. Therefore, for functions with continuity properties, it suggests that all such functions are not one-way. It is shown here that in the formal complexity theory of real functions, this nonexistence of continuous one-way functions can be proved for one-to-one one-dimensional real functions, but fails for one-to-one two-dimensional real functions, if certain strong discrete one-way functions exist. Furthermore, for k-to-one functions, we can prove the existence of four-to-one one-dimensional one-way functions under the same assumption of the existence of strong discrete one-way functions. (A function f is k-to-one if for any y there exist at most k distinct values x such that f ( x ) = y.)

Details DOI

TCS Journal 2021 Journal Article

Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks

  • Chuanwen Luo
  • Wenping Chen
  • Deying Li
  • Yongcai Wang
  • Hongwei Du
  • Lidong Wu
  • Weili Wu

Unmanned Aerial Vehicles (UAVs) are expected to be important components in the upcoming wireless communication field, which are increasingly used as data collectors to gather sensory data from Wireless Sensor Networks (WSNs) due to their high mobility, flexible deployment. Since the storage capacity and lifetime of sensors are increasing with the development of science and technology, sensors can store more and more sensing data about the monitoring area. However, due to the energy limitation of UAVs and a large amount of data carried by sensors, we can not collect all data from WSN within the limited time. Therefore, in this paper, we investigate two problems: (1) without the energy limitation of UAV, how to optimize the trajectory of UAV to minimize the sum of traveling time and data transmission time of UAV while guaranteeing the amount of data collected from each sensor reaches to a certain proportion of the original data, which is called the Minimizing Transportation and Communication Latency (MTCL) problem; (2) given the limited budget of UAV, how to find the optimal trajectory of UAV to maximize the minimum ratio of the collected data to the stored data among all sensors, which is called the Maximizing Data Collection Proportion (MDCP) problem. We first prove that both the problems are NP-Complete. Then we study a special case of the MTCL problem, which is called the MTCL-disjoint problem, in which any pair of data collection areas are disjoint, and we propose an approximation algorithm to solve the MTCL-disjoint problem. Based on the MTCL-disjoint problem, we propose an approximation algorithm for the general MTCL problem. Afterward, an approximation algorithm for the MDCP problem is proposed on the basis of the algorithm for the MTCL problem. Finally, we present numerical results in different scenarios to assess the effectiveness of the proposed algorithms.

Details DOI
v2026.09.13