• 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. © 2024 Elsevier B.V.

Keyword:

Combinatorial mathematics Approximation algorithms

Author Community:

  • [ 1 ] [Chang, Hong]School of Mathematical Science, Institute of Mathematics, Ministry of Education Key Laboratory of NSLSCS, Nanjing Normal University, Nanjing; 210023, China
  • [ 2 ] [Jin, Jing]College of Taizhou, Nanjing Normal University, Taizhou; 225300, China
  • [ 3 ] [Liu, Zhicheng]Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing; 100124, China
  • [ 4 ] [Du, Donglei]Faculty of Management, University of New Brunswick, Fredericton; NB; E3B 5A3, Canada
  • [ 5 ] [Zhang, Xiaoyan]School of Mathematical Science, Institute of Mathematics, Ministry of Education Key Laboratory of NSLSCS, Nanjing Normal University, Nanjing; 210023, China

Reprint Author's Address:

Email:

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

Affiliated Colleges:

Online/Total:747/10616180
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.