Browsing by Author "Ko, Ker-I"

Now showing 1 - 4 of 4

An approximation algorithm for maximum weight budgeted connected set cover
(2016-05)
Ran, Yingli
;
Zhang, Zhao
;
Ko, Ker-I
;
Liang, Jun
;
資訊工程學系
This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected graph (called communication graph) on vertex set , and a budget , the MWBCSC problem is to select a subcollection such that the cost , the subgraph of induced by is connected, and the total weight of elements covered by (that is ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio , where is the maximum degree of graph and is the number of sets in . In particular, if every set has cost at most , the performance ratio can be improved to .
Centralized and decentralized rumor blocking problems
(2017-07-01)
Chen, Xin
;
Nong, Qingqin
;
Feng, Yan
;
Cao, Yongchang
;
Gong, Suning
This paper consists of two parts. In the first part, we study a centralized rumor blocking problem with a novel social objective function different from those in the literature. We will show that this objective function is non-decreasing and submodular and hence corresponding rumor blocking problem has a greedy approximation with objective function value at least of the optimal. In the second part, we study a decentralized rumor blocking problem with two selfish protectors, which falls into a 2-player non-cooperate game model. We will show that this game is a basic valid utility system and hence the social utility of any Nash equilibrium in the game is at least a half of the optimal social utility.
Competitive profit maximization in social networks
(2017-09-19)
Li, Weian
;
Liu, Wenjing
;
Chen, Tiantian
;
Qu, Xiaoying
;
Fang, Qizhi
We study the competitive profit maximization problem in a social network, which can be viewed as the profit maximization problem in a game-theoretic setting. We formulate two models called the profit maximization-agent (PM-A) game and the profit maximization-society (PM-S) game. By reducing them to be valid utility systems, we show that any Nash equilibrium provides an excepted social utility within a factor 1/2 (subject to a function-dependent additive term) of the optimum in the PM-A game and a factor of 1/2 of the optimum in the PM-S game. Furthermore, for the PM-S game, a polynomial-time algorithm is given for each player that can approximate the best response within a factor (1 - 1/e). (C) 2017 Elsevier B.V. All rights reserved.
On parallel complexity of analytic functions
(2013-06-10)
Yu, Fuxiang
;
Ko, Ker-I
;
資訊工程學系
;
Department of Computer Science
In this paper, we study the parallel complexity of analytic functions. We investigate the complexity of computing the derivatives, integrals, and zeros of NC or logarithmic-space computable analytic functions, where NC denotes the complexity class of sets acceptable by polynomial-size, polylogarithmic-depth, uniform Boolean circuits. It is shown that the derivatives and integrals of NC (or logarithmic-space) computable analytic functions remain NC (or, respectively, logarithmic-space) computable. We also study the problem of finding all zeros of an NC computable analytic function inside an NC computable Jordan curve, and show that, under a uniformity condition on the function values on the Jordan curve, all zeros can be found in NC. (c) 2013 Elsevier B.V. All rights reserved.