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

author:

Liu, Zhicheng (Liu, Zhicheng.) [1] | Guo, Longkun (Guo, Longkun.) [2] | Du, Donglei (Du, Donglei.) [3] | Xu, Dachuan (Xu, Dachuan.) [4] | Zhang, Xiaoyan (Zhang, Xiaoyan.) [5]

Indexed by:

EI

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 α)) -bifactor approximation ratio, improving the previous (1 / (2 α) , 1 / (2 α)) -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-kfe-1,1-kge-(1-kg)}-approximation algorithm, improving the previous kf-1(1-e-kf(1-kg))-approximation ratio, where kf and kg 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-kg(1-kg)kf+p-approximation ratio to min{p+1-kfp(p+1),(1-kgp+kg(1-kg)2p+(1-kg)2)}. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Keyword:

Approximation algorithms Balancing Combinatorial mathematics Data Science

Community:

  • [ 1 ] [Liu, Zhicheng]College of Taizhou, Nanjing Normal University, Taizhou; 225300, China
  • [ 2 ] [Guo, Longkun]School of Computer Science and Bigdata, Fuzhou University, Fuzhou; 350116, China
  • [ 3 ] [Du, Donglei]Faculty of Management, University of New Brunswick, Fredericton; NB; E3B 5A3, Canada
  • [ 4 ] [Xu, Dachuan]Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing; 100124, China
  • [ 5 ] [Zhang, Xiaoyan]School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing; 210023, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Journal of Global Optimization

ISSN: 0925-5001

Year: 2022

Issue: 1

Volume: 82

Page: 179-194

1 . 8

JCR@2022

1 . 3 0 0

JCR@2023

ESI HC Threshold:66

JCR Journal Grade:2

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 6

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:1291/13880119
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1