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

Author:

Chang, Hong (Chang, Hong.) | Jin, Jing (Jin, Jing.) | Liu, Zhicheng (Liu, Zhicheng.) | Du, Donglei (Du, Donglei.) | Zhang, Xiaoyan (Zhang, Xiaoyan.)

Indexed by:

EI Scopus SCIE

Abstract:

The BP problem maximizes the sum of a suBmodular function and a suPermodular function(BP) subject to some constraints, where both functions are nonnegative and monotonic. This problem has been widely studied under the single-stage setting. In this paper, we consider a variant of the BP maximization problem. The problem is a two-stage BP maximization problem subject to a p-matroid constraint, for which we propose an approximation algorithm with constant approximation ratio parameterized by the curvatures of the two functions involved.

Keyword:

Submodular term Curvature p-matroid constraint Two-stage BP maximization Supermodular term

Author Community:

  • [ 1 ] [Chang, Hong]Nanjing Normal Univ, Inst Math, Sch Math Sci, Nanjing 210023, Peoples R China
  • [ 2 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Sch Math Sci, Nanjing 210023, Peoples R China
  • [ 3 ] [Chang, Hong]Nanjing Normal Univ, Key Lab NSLSCS, Minist Educ, Nanjing 210023, Peoples R China
  • [ 4 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Key Lab NSLSCS, Minist Educ, Nanjing 210023, Peoples R China
  • [ 5 ] [Jin, Jing]Nanjing Normal Univ, Coll Taizhou, Taizhou 225300, Peoples R China
  • [ 6 ] [Liu, Zhicheng]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 7 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada

Reprint Author's Address:

  • [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Sch Math Sci, Nanjing 210023, Peoples R China;;[Zhang, Xiaoyan]Nanjing Normal Univ, Key Lab NSLSCS, Minist Educ, Nanjing 210023, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2024

Volume: 994

1 . 1 0 0

JCR@2022

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:667/5335683
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.