• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Liu, Zhicheng (Liu, Zhicheng.) | Guo, Longkun (Guo, Longkun.) | Du, Donglei (Du, Donglei.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Xiaoyan (Zhang, Xiaoyan.)

Indexed by:

EI Scopus SCIE

Abstract:

Relevance and diversity are two desirable properties in data retrieval applications, an important field in data science and machine learning. In this paper, we consider three maximization problems to balance these two factors. The objective function in each problem is the sum of a monotone submodular function f and a supermodular function g, where f and g capture the relevance and diversity of any feasible solution, respectively. In the first problem, we consider a special supermodular diversity function g of a sum-sum format satisfying the relaxed triangle inequality, for which we propose a greedy-type approximation algorithm with an (1 -1/e, 1/(2 alpha))-bifactor approximation ratio, improving the previous (1/(2 alpha), 1/(2 alpha))-bifactor approximation ratio. In the second problem, we consider an arbitrary supermodular diversity function g, for which we propose a distorted greedy method to give a min {1 - k(f)e(-1), 1 - k(g)e(-(1-kg))}-approximation algorithm, improving the previous k(f)(-1) (1 - e(-kf(1-kg)))-approximation ratio, where k(f) and k(g) are the curvatures of the submodular function f and the supermodular funciton g, respectively. In the third problem, we generalize the uniform matroid constraint to the p matroid constraints, for which we present a local search algorithm to improve the previous 1-k(g)/(1-k(g))k(f)+p-approximation ratio to min {p+1-k(f)/p(p+1), (1-k(g)/p + k(g)(1-k(g))(2)/p+(1-k(g))(2))}.

Keyword:

Greedy algorithm Max-sum diversification Curvature Matroid Supermodular Local search submodular

Author Community:

  • [ 1 ] [Liu, Zhicheng]Nanjing Normal Univ, Coll Taizhou, Taizhou 225300, Peoples R China
  • [ 2 ] [Guo, Longkun]Fuzhou Univ, Sch Comp Sci & Bigdata, Fuzhou 350116, Peoples R China
  • [ 3 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada
  • [ 4 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 5 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Peoples R China
  • [ 6 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Peoples R China

Reprint Author's Address:

  • [Zhang, Xiaoyan]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Peoples R China;;[Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Peoples R China

Show more details

Related Keywords:

Source :

JOURNAL OF GLOBAL OPTIMIZATION

ISSN: 0925-5001

Year: 2021

Issue: 1

Volume: 82

Page: 179-194

1 . 8 0 0

JCR@2022

ESI Discipline: ENGINEERING;

ESI HC Threshold:87

JCR Journal Grade:2

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 5

Affiliated Colleges:

Online/Total:1468/10993341
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.