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

Author:

Jiang, Yanjun (Jiang, Yanjun.) | Wang, Yijing (Wang, Yijing.) | Yang, Ruiqi (Yang, Ruiqi.) | Ye, Weina (Ye, Weina.)

Indexed by:

CPCI-S EI Scopus

Abstract:

Utilizing approximation algorithm, there has been a large quantity of work on optimization for submodular functions since the 1970s. As a variant, k-submodular function appears in many fields to match with the developing background, in which the outputted sets changes from one to k. Because of the application of submodularity, some concepts and parameters describing the closeness to submodular function are generated, for example approximately submodular set function and diminishing-return (DR) ratio. In our discussion, the k-dimension set function with matroid constraint we will maximize may not have access to the submodularity. However it is an approximately non-k-submodular set function which contains DR ratio. By the greedy technique, we obtain the approximation algorithms. When the value of the DR ratio is set one, some known results are covered.

Keyword:

Approximation algorithm Matroid k-submodular set function Greedy

Author Community:

  • [ 1 ] [Jiang, Yanjun]Ludong Univ, Sch Math & Stat Sci, Yantai 264025, Peoples R China
  • [ 2 ] [Wang, Yijing]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 3 ] [Yang, Ruiqi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Ye, Weina]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 5 ] [Yang, Ruiqi]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022

ISSN: 0302-9743

Year: 2022

Volume: 13571

Page: 11-20

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: 6

Affiliated Colleges:

Online/Total:669/10645646
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.