Search

Your search keyword '"Du, Ding"' showing total 4,820 results
Start Over Author "Du, Ding"

Refine your results

4,820 results on '"Du, Ding"'

6. Multi-Task Diffusion Incentive Design for Mobile Crowdsourcing in Social Networks

Author

Guo, Jianxiong, Ni, Qiufen, Wu, Weili, and Du, Ding-Zhu

Subjects
Computer Science - Social and Information Networks, Computer Science - Computer Science and Game Theory
Abstract

Mobile Crowdsourcing (MCS) is a novel distributed computing paradigm that recruits skilled workers to perform location-dependent tasks. A number of mature incentive mechanisms have been proposed to address the worker recruitment problem in MCS systems. However, they all assume that there is a large enough worker pool and a sufficient number of users can be selected. This may be impossible in large-scale crowdsourcing environments. To address this challenge, we consider the MCS system defined on a location-aware social network provided by a social platform. In this system, we can recruit a small number of seed workers from the existing worker pool to spread the information of multiple tasks in the social network, thus attracting more users to perform tasks. In this paper, we propose a Multi-Task Diffusion Maximization (MT-DM) problem that aims to maximize the total utility of performing multiple crowdsourcing tasks under the budget. To accommodate multiple tasks diffusion over a social network, we create a multi-task diffusion model, and based on this model, we design an auction-based incentive mechanism, MT-DM-L. To deal with the high complexity of computing the multi-task diffusion, we adopt Multi-Task Reverse Reachable (MT-RR) sets to approximate the utility of information diffusion efficiently. Through both complete theoretical analysis and extensive simulations by using real-world datasets, we validate that our estimation for the spread of multi-task diffusion is accurate and the proposed mechanism achieves individual rationality, truthfulness, computational efficiency, and $(1-1/\sqrt{e}-\varepsilon)$ approximation with at least $1-\delta$ probability., Comment: 14 pages

Published
2023
Full Text
View/download PDF

7. A New Approximation Algorithm for Minimum-Weight $(1,m)$--Connected Dominating Set

Author

Zhou, Jiao, Ran, Yingli, Pardalos, Panos M., Zhang, Zhao, Tang, Shaojie, and Du, Ding-Zhu

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, 68W25, F.2.2
Abstract

Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least $m$ neighbors in the subset, then the node subset is called a $(1,m)$CDS. The minimum-weight $(1,m)$CDS problem aims at finding a $(1,m)$CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem with approximation ratio $2H(\delta_{\max}+m-1)$, where $\delta_{\max}$ is the maximum degree of the given graph and $H(\cdot)$ is the Harmonic function, i.e., $H(k)=\sum_{i=1}^k \frac{1}{i}$.

Published
2023

8. Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems

Author

Zhang, Yaoyao, Zhu, Chaojie, Tang, Shaojie, Ran, Ringli, Du, Ding-Zhu, and Zhang, Zhao

Subjects
Computer Science - Neural and Evolutionary Computing, Computer Science - Discrete Mathematics, 68w25, 68w15, F.2.2
Abstract

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.

Published
2022

9. Composite Community-Aware Diversified Influence Maximization with Efficient Approximation

Author

Guo, Jianxiong, Ni, Qiufen, Wu, Weili, and Du, Ding-Zhu

Subjects
Computer Science - Social and Information Networks, Mathematics - Combinatorics
Abstract

Influence Maximization (IM) is a famous topic in mobile networks and social computing, which aims at finding a small subset of users to maximize the influence spread through online information cascade. Recently, some careful researchers paid attention to diversity of information dissemination, especially community-aware diversity, and formulated the diversified IM problem. The diversity is ubiquitous in a lot of real-world applications, but they are all based on a given community structure. In social networks, we can form heterogeneous community structures for the same group of users according to different metrics. Therefore, how to quantify the diversity based on multiple community structures is an interesting question. In this paper, we propose the Composite Community-Aware Diversified IM (CC-DIM) problem, which aims at selecting a seed set to maximize the influence spread and the composite diversity over all possible community structures under consideration. To address the NP-hardness of CC-DIM problem, we adopt the technique of reverse influence sampling and design a random Generalized Reverse Reachable (G-RR) set to estimate the objective function. The composition of a random G-RR set is much more complex than the RR set used for the IM problem, which will lead to inefficiency of traditional sampling-based approximation algorithms. Because of this, we further propose a two-stage algorithm, Generalized HIST (G-HIST). It can not only return a $(1-1/e-\varepsilon)$ approximate solution with at least $(1-\delta)$ probability, but also improve the efficiency of sampling and ease the difficulty of searching by significantly reducing the average size of G-RR sets. Finally, we evaluate our G-HIST on real datasets against existing algorithms. The experimental results show the effectiveness of our proposed algorithm and its superiority over other baseline algorithms., Comment: 15 pages

Published
2022
Full Text
View/download PDF

13. Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set

Author

Zhu, Chaojie, Ran, Yingli, Zhang, Zhao, and Du, Ding-Zhu

Subjects
Computer Science - Discrete Mathematics, 68W02, 68R02, F.2.2
Abstract

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\Delta)$, where $n$ and $\Delta$ are the number of vertices and the maximum degree of graph $G$, respectively., Comment: 20 pages, 4 figures

Published
2022

14. Machine Learning-Based Rumor Controlling

Author

Su, Ke, Garg, Priyanshi, Wu, Weili, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Balomenos, Konstantinos P., editor, and Fytopoulos, Antonios, editor

Published
2023
Full Text
View/download PDF

15. Formulate Full View Camera Sensor Coverage by Using Group Set Coverage

Author

Du, Hongwei, Zhang, Zhao, Duan, Zhenhua, Tian, Cong, Du, Ding-Zhu, Akan, Ozgur, Editorial Board Member, Bellavista, Paolo, Editorial Board Member, Cao, Jiannong, Editorial Board Member, Coulson, Geoffrey, Editorial Board Member, Dressler, Falko, Editorial Board Member, Ferrari, Domenico, Editorial Board Member, Gerla, Mario, Editorial Board Member, Kobayashi, Hisashi, Editorial Board Member, Palazzo, Sergio, Editorial Board Member, Sahni, Sartaj, Editorial Board Member, Shen, Xuemin, Editorial Board Member, Stan, Mircea, Editorial Board Member, Jia, Xiaohua, Editorial Board Member, Zomaya, Albert Y., Editorial Board Member, Haas, Zygmunt J., editor, Prakash, Ravi, editor, Ammari, Habib, editor, and Wu, Weili, editor

Published
2023
Full Text
View/download PDF

17. A Double Auction for Charging Scheduling among Vehicles Using DAG-Blockchains

Author

Guo, Jianxiong, Ding, Xingjian, Wu, Weili, and Du, Ding-Zhu

Subjects
Computer Science - Networking and Internet Architecture, Computer Science - Computer Science and Game Theory
Abstract

Electric Vehicles (EVs) are becoming more and more popular in our daily life, which replaces traditional fuel vehicles to reduce carbon emissions and protect the environment. EVs need to be charged, but the number of charging piles in a Charging Station (CS) is limited and charging is usually more time-consuming than fueling. According to this scenario, we propose a secure and efficient charging scheduling system based on a Directed Acyclic Graph (DAG)-blockchain and double auction mechanism. In a smart area, it attempts to assign EVs to the available CSs in the light of their submitted charging requests and status information. First, we design a lightweight charging scheduling framework that integrates DAG-blockchain and modern cryptography technology to ensure security and scalability during performing scheduling and completing tradings. In this process, a constrained multi-item double auction problem is formulated because of the limited charging resources in a CS, which motivates EVs and CSs in this area to participate in the market based on their preferences and statuses. Due to this constraint, our problem is more complicated and harder to achieve truthfulness as well as system efficiency compared to the existing double auction model. To adapt to it, we propose two algorithms, namely Truthful Mechanism for Charging (TMC) and Efficient Mechanism for Charging (EMC), to determine an assignment between EVs and CSs and pricing strategies. Then, both theoretical analysis and numerical simulations show the correctness and effectiveness of our proposed algorithms.

Published
2020
Full Text
View/download PDF

18. Population Monotonic Allocation Schemes for Vertex Cover Games

Author

Xiao, Han, Fang, Qizhi, and Du, Ding-Zhu

Subjects
Computer Science - Computer Science and Game Theory, Computer Science - Discrete Mathematics, 05C57, 91A12, 91A43, 91A46
Abstract

For vertex cover games (introduced by Deng et al., Math. Oper. Res., 24:751-766, 1999), we investigate population monotonic allocation schemes (introduced by Sprumont, Games Econ. Behav., 2: 378-394, 1990). We show that the existence of a population monotonic allocation scheme (PMAS for short) for vertex cover games can be determined efficiently and that a PMAS, if exists, can be constructed accordingly. We also show that integral PMAS-es for vertex cover games can be characterized with stable matchings and be enumerated by employing Gale-Shapley algorithm (introduced by Gale and Shapley, Amer. Math. Monthly, 69:9-15, 1962)., Comment: To appear in Theoretical Computer Science

Published
2020
Full Text
View/download PDF

19. Linear Programming

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

20. Relaxation and Rounding

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

21. Introduction

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

22. NP-Hard Problems and Approximation Algorithms

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

23. Primal-Dual Methods and Minimum Cost Flow

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

24. Restriction and Steiner Tree

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

25. Incremental Method and Maximum Network Flow

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

26. Dynamic Programming and Shortest Path

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

27. Greedy Algorithm and Spanning Tree

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

28. Divide-and-Conquer

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

29. Nonsubmodular Optimization

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

30. Greedy Approximation and Submodular Optimization

Author

Du, Ding-Zhu, Pardalos, Panos, Hu, Xiaodong, Wu, Weili, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Advisory Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Hu, Xiaodong, and Wu, Weili

Published
2022
Full Text
View/download PDF

32. Beyond Uniform Reverse Sampling: A Hybrid Sampling Technique for Misinformation Prevention

Author

Tong, Gunagmo and Du, Ding-Zhu

Subjects
Computer Science - Social and Information Networks, Computer Science - Data Structures and Algorithms
Abstract

Online misinformation has been considered as one of the top global risks as it may cause serious consequences such as economic damages and public panic. The misinformation prevention problem aims at generating a positive cascade with appropriate seed nodes in order to compete against the misinformation. In this paper, we study the misinformation prevention problem under the prominent independent cascade model. Due to the #P-hardness in computing influence, the core problem is to design effective sampling methods to estimate the function value. The main contribution of this paper is a novel sampling method. Different from the classic reverse sampling technique which treats all nodes equally and samples the node uniformly, the proposed method proceeds with a hybrid sampling process which is able to attach high weights to the users who are prone to be affected by the misinformation. Consequently, the new sampling method is more powerful in generating effective samples used for computing seed nodes for the positive cascade. Based on the new hybrid sample technique, we design an algorithm offering a $(1-1/e-\epsilon)$-approximation. We experimentally evaluate the proposed method on extensive datasets and show that it significantly outperforms the state-of-the-art solutions., Comment: Type fixed

Published
2019

35. Distance Magic Labeling of the Halved Folded n-Cube

Author

Tian, Yi, Kang, Na, Wu, Weili, Du, Ding-Zhu, Gao, Suogang, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Ni, Qiufen, editor, and Wu, Weili, editor

Published
2022
Full Text
View/download PDF

36. Black-Box and Data-Driven Computation

Author

Jin, Rong, Wu, Weili, Thai, My T., Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, and Rasskazova, Varvara, editor

Published
2021
Full Text
View/download PDF

41. Approximation Algorithm for the Partial Set Multi-Cover Problem

Author

Shi, Yishuo, Ran, Yingli, Zhang, Zhao, Willson, James, Tong, Guangmo, and Du, Ding-Zhu

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, 68W25, G.2.1
Abstract

Partial set cover problem and set multi-cover problem are two generalizations of set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set $E$, a collection of sets $\mathcal S\subseteq 2^E$, a total covering ratio $q$ which is a constant between 0 and 1, each set $S\in\mathcal S$ is associated with a cost $c_S$, each element $e\in E$ is associated with a covering requirement $r_e$, the goal is to find a minimum cost sub-collection $\mathcal S'\subseteq\mathcal S$ to fully cover at least $q|E|$ elements, where element $e$ is fully covered if it belongs to at least $r_e$ sets of $\mathcal S'$. Denote by $r_{\max}=\max\{r_e\colon e\in E\}$ the maximum covering requirement. We present an $(O(\frac{r_{\max}\log^2n}{\varepsilon}),1-\varepsilon)$-bicriteria approximation algorithm, that is, the output of our algorithm has cost at most $O(\frac{r_{\max}\log^2 n}{\varepsilon})$ times of the optimal value while the number of fully covered elements is at least $(1-\varepsilon)q|E|$.

Published
2018
Full Text
View/download PDF

42. An Approximation Algorithm for Active Friending in Online Social Networks

Author

Tong, Guangmo, Wang, Ruiqi, Li, Xiang, Wu, Weili, and Du, Ding-Zhu

Subjects
Computer Science - Social and Information Networks
Abstract

Guiding users to actively expanding their online social circles is one of the primary strategies for enhancing user participation and growing online social networks. In this paper, we study the active friending problem which aims at providing users with the strategy for methodically sending invitations to successfully build a friendship with target users. We consider the prominent linear threshold model for the friending process and formulate the active friending problem as an optimization problem. The key observation is the relationship between the active friending problem and the minimum subset cover problem, based on which we present the first randomized algorithm with a data-independent approximation ratio and a controllable success probability for general graphs. The performance of the proposed algorithm is theoretically analyzed and supported by encouraging simulation results done on extensive datasets.

Published
2018

43. On Misinformation Containment in Online Social Networks

Author

Tong, Guangmo, Wu, Weili, and Du, Ding-Zhu

Subjects
Computer Science - Social and Information Networks
Abstract

The widespread online misinformation could cause public panic and serious economic damages. The misinformation containment problem aims at limiting the spread of misinformation in online social networks by launching competing campaigns. Motivated by realistic scenarios, we present the first analysis of the misinformation containment problem for the case when an arbitrary number of cascades are allowed. This paper makes four contributions. First, we provide a formal model for multi-cascade diffusion and introduce an important concept called as cascade priority. Second, we show that the misinformation containment problem cannot be approximated within a factor of $\Omega(2^{\log^{1-\epsilon}n^4})$ in polynomial time unless $NP \subseteq DTIME(n^{\polylog{n}})$. Third, we introduce several types of cascade priority that are frequently seen in real social networks. Finally, we design novel algorithms for solving the misinformation containment problem. The effectiveness of the proposed algorithm is supported by encouraging experimental results., Comment: NIPS 2018

Published
2018

44. Coupon Advertising in Online Social Systems: Algorithms and Sampling Techniques

Author

Tong, Guangmo, Wu, Weili, and Du, Ding-Zhu

Subjects
Computer Science - Social and Information Networks
Abstract

Online social systems have become important platforms for viral marketing where the advertising of products is carried out with the communication of users. After adopting the product, the seed buyers may spread the information to their friends via online messages e.g. posts and tweets. In another issue, electronic coupon system is one of the relevant promotion vehicles that help manufacturers and retailers attract more potential customers. By offering coupons to seed buyers, there is a chance to convince the influential users who are, however, at first not very interested in the product. In this paper, we propose a coupon based online influence model and consider the problem that how to maximize the profit by selecting appropriate seed buyers. The considered problem herein is markedly different from other influence related problems as its objective function is not monotone. We provide an algorithmic analysis and give several algorithms designed with different sampling techniques. In particular, we propose the RA-T and RA-S algorithms which are not only provably effective but also scalable on large datasets. The proposed theoretical results are evaluated by extensive experiments done on large-scale real-world social networks. The analysis of this paper also provides an algorithmic framework for non-monotone submodular maximization problems in social networks., Comment: Under review

Published
2018

45. Grid-Based Deployment

Author

Wu, Weili, Zhang, Zhao, Lee, Wonjun, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Wu, Weili, Zhang, Zhao, and Lee, Wonjun

Published
2020
Full Text
View/download PDF

46. Heterogeneous Sensors

Author

Wu, Weili, Zhang, Zhao, Lee, Wonjun, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Wu, Weili, Zhang, Zhao, and Lee, Wonjun

Published
2020
Full Text
View/download PDF

47. k-Coverage

Author

Wu, Weili, Zhang, Zhao, Lee, Wonjun, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Wu, Weili, Zhang, Zhao, and Lee, Wonjun

Published
2020
Full Text
View/download PDF

48. Fundamental Issues

Author

Wu, Weili, Zhang, Zhao, Lee, Wonjun, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Wu, Weili, Zhang, Zhao, and Lee, Wonjun

Published
2020
Full Text
View/download PDF

49. Weighted Sensor Cover

Author

Wu, Weili, Zhang, Zhao, Lee, Wonjun, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Wu, Weili, Zhang, Zhao, and Lee, Wonjun

Published
2020
Full Text
View/download PDF

50. Lifetime of Coverage

Author

Wu, Weili, Zhang, Zhao, Lee, Wonjun, Du, Ding-Zhu, Pardalos, Panos M., Series Editor, Thai, My T., Series Editor, Du, Ding-Zhu, Honorary Editor, Belavkin, Roman V., Advisory Editor, Birge, John R., Advisory Editor, Butenko, Sergiy, Advisory Editor, Giannessi, Franco, Advisory Editor, Kumar, Vipin, Advisory Editor, Nagurney, Anna, Advisory Editor, Pei, Jun, Advisory Editor, Prokopyev, Oleg, Advisory Editor, Rebennack, Steffen, Advisory Editor, Resende, Mauricio, Advisory Editor, Terlaky, Tamás, Advisory Editor, Vu, Van, Advisory Editor, Vrahatis, Michael N., Associate Editor, Xue, Guoliang, Advisory Editor, Ye, Yinyu, Advisory Editor, Wu, Weili, Zhang, Zhao, and Lee, Wonjun

Published
2020
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results