{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:48Z","timestamp":1754152308549,"version":"3.41.2"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2021MA100"],"award-info":[{"award-number":["ZR2021MA100"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2020MA029"],"award-info":[{"award-number":["ZR2020MA029"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12001335"],"award-info":[{"award-number":["12001335"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:p> Both matroid means and knapsack means are variations of the classic [Formula: see text]-means problem in which we replace the cardinality constraint by matroid constraint or knapsack constraint respectively. In this paper, we give a 64-approximation algorithm for the matroid means problem and a [Formula: see text]-approximation algorithm for the knapsack means problem by using a simpler and more efficient rounding method. We improve previous 304 approximate ratio for the former and 20016 approximate ratio for the latter. In the rounding process, the application of integrality of the intersection of submodular (or matroid) polyhedra provides strong theoretical support. Moreover, we extend this method to matroid means problem with penalties, and give 64 and 880-approximate algorithms for uniform penalties and nonuniform penalties problem. <\/jats:p>","DOI":"10.1142\/s012905412246008x","type":"journal-article","created":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T02:50:21Z","timestamp":1675479021000},"page":"709-729","source":"Crossref","is-referenced-by-count":0,"title":["Improved Approximation Algorithms for Matroid and Knapsack Means Problems"],"prefix":"10.1142","volume":"36","author":[{"given":"Ao","family":"Zhao","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China"}]},{"given":"Yang","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6038-4219","authenticated-orcid":false,"given":"Qian","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,2,3]]},"reference":[{"key":"S012905412246008XBIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"S012905412246008XBIB002","first-page":"1027","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Arthur D.","year":"2007"},{"key":"S012905412246008XBIB003","doi-asserted-by":"publisher","DOI":"10.1137\/080715421"},{"key":"S012905412246008XBIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0294-4"},{"key":"S012905412246008XBIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_17"},{"key":"S012905412246008XBIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0010-1"},{"key":"S012905412246008XBIB007","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520011"},{"key":"S012905412246008XBIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9547-9"},{"key":"S012905412246008XBIB009","first-page":"1","volume-title":"Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"145","author":"Kale S.","year":"2019"},{"key":"S012905412246008XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"S012905412246008XBIB011","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.84"},{"key":"S012905412246008XBIB012","doi-asserted-by":"publisher","DOI":"10.1145\/2963170"},{"journal-title":"Asia-Pacific Journal of Operational Research","year":"2022","author":"Zhao A.","key":"S012905412246008XBIB013"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412246008X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:43:53Z","timestamp":1753155833000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905412246008X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,3]]},"references-count":13,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1142\/S012905412246008X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412246008x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,2,3]]}}}