{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:41Z","timestamp":1740122381784,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11801589","11771245"],"award-info":[{"award-number":["11801589","11771245"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11371216"],"award-info":[{"award-number":["11371216"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s10878-021-00754-w","type":"journal-article","created":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T10:03:26Z","timestamp":1621505006000},"page":"200-225","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Some graph optimization problems with weights satisfying linear constraints"],"prefix":"10.1007","volume":"43","author":[{"given":"Kameng","family":"Nip","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianning","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenbo","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,20]]},"reference":[{"key":"754_CR1","volume-title":"Network flows: theory, algorithms, and applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, New Jersey"},{"doi-asserted-by":"crossref","unstructured":"Bar-Yehuda R, Bendel K, Freund A, Rawitz D (2004) Local ratio: a unified framework for approximation algorithms. ACM Comput Surv 36(4):422\u2013463","key":"754_CR2","DOI":"10.1145\/1041680.1041683"},{"issue":"2","key":"754_CR3","first-page":"97","volume":"17","author":"S Burer","year":"2012","unstructured":"Burer S, Letchford AN (2012) Non-convex mixed-integer nonlinear programming: a survey. Surv Oper Res Manag Scie 17(2):97\u2013106","journal-title":"Surv Oper Res Manag Scie"},{"key":"754_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment problems","author":"R Burkard","year":"2009","unstructured":"Burkard R, Dell\u2019Amico M, Martello S (2009) Assignment problems. Society for Industrial and Applied Mathematics, Philadelphia"},{"key":"754_CR5","volume-title":"Design and analysis of approximation algorithms","author":"DZ Du","year":"2011","unstructured":"Du DZ, Ko KI, Hu X (2011) Design and analysis of approximation algorithms. Springer, New York"},{"issue":"1","key":"754_CR6","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439\u2013485","journal-title":"Ann Math"},{"key":"754_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"754_CR8","first-page":"32","volume-title":"History of mathematical programming\u2013a collection of personal reminiscences","author":"J Edmonds","year":"1961","unstructured":"Edmonds J (1961) A glimpse of heaven. In: Lenstra J, Kan AR, Schrijver A (eds) History of mathematical programming\u2013a collection of personal reminiscences. Centrum Wiskunde & Informatica, Amsterdam, pp 32\u201354"},{"key":"754_CR9","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees, and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"issue":"2","key":"754_CR10","first-page":"127","volume":"1","author":"I Fagoyinbo","year":"2010","unstructured":"Fagoyinbo I, Ajibode I (2010) Application of linear programming techniques in the effective use of resources for staff training. J Emerg Trends Eng Appl Sci 1(2):127\u2013132","journal-title":"J Emerg Trends Eng Appl Sci"},{"issue":"3","key":"754_CR11","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J ACM 34(3):596\u2013615","journal-title":"J ACM"},{"key":"754_CR12","first-page":"2931","volume":"1","author":"E Filiol","year":"2007","unstructured":"Filiol E, Franc E, Gubbioli A, Moquet B, Roblot G (2007) Combinatorial optimisation of worm propagation on an unknown network. Int J Comput Electr Autom Control Inf Eng 1:2931\u20132937","journal-title":"Int J Comput Electr Autom Control Inf Eng"},{"key":"754_CR13","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"unstructured":"Gupta KM (2014) Application of linear programming techniques for staff training. Int J Eng Innov Technol 3(12)","key":"754_CR14"},{"key":"754_CR15","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.omega.2019.08.009","volume":"97","author":"VV Gusev","year":"2020","unstructured":"Gusev VV (2020) The vertex cover game: application to transport networks. Omega 97:102","journal-title":"Omega"},{"key":"754_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Springer, Boston, pp 85\u2013103"},{"issue":"3","key":"754_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot S, Regev O (2008) Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J Comput Syst Sci 74(3):335\u2013349","journal-title":"J Comput Syst Sci"},{"key":"754_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial optimization: theory and algorithms","author":"B Korte","year":"2012","unstructured":"Korte B, Vygen J (2012) Combinatorial optimization: theory and algorithms, 4th edn. Springer, Berlin","edition":"4"},{"key":"754_CR19","volume-title":"Algorithm design","author":"J Kleinberg","year":"2006","unstructured":"Kleinberg J, Tardos \u00c9 (2006) Algorithm design. Pearson Education, New York"},{"doi-asserted-by":"crossref","unstructured":"K\u00f6ppe M (2011) On the complexity of nonlinear mixed-integer optimization. In: Lee J, Leyffer S (eds) Mixed-integer nonlinear programming. IMA volumes in mathematics and its applications, vol 154. Springer, Berlin, pp 533\u2013558","key":"754_CR20","DOI":"10.1007\/978-1-4614-1927-3_19"},{"issue":"1 & 2","key":"754_CR21","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2(1 & 2):83\u201397","journal-title":"Naval Res Logist Q"},{"key":"754_CR22","volume-title":"Linear and nonlinear programming","author":"DG Luenberger","year":"2015","unstructured":"Luenberger DG, Ye Y (2015) Linear and nonlinear programming. Springer, New York"},{"issue":"2","key":"754_CR23","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/j.ejor.2016.02.028","volume":"253","author":"K Nip","year":"2016","unstructured":"Nip K, Wang Z, Wang Z (2016) Scheduling under linear constraints. Eur J Oper Res 253(2):290\u2013297","journal-title":"Eur J Oper Res"},{"issue":"3","key":"754_CR24","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s10898-017-0540-y","volume":"69","author":"K Nip","year":"2017","unstructured":"Nip K, Wang Z, Wang Z (2017) Knapsack with variable weights satisfying linear constraints. J Global Optim 69(3):713\u2013725","journal-title":"J Global Optim"},{"key":"754_CR25","volume-title":"Combinatorial optimization: algorithms and complexity","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Courier Dover Publications, New York"},{"issue":"1","key":"754_CR26","first-page":"83","volume":"3","author":"K Sachdeva","year":"2012","unstructured":"Sachdeva K (2012) Applications of graphs in real-life. Int J Adv Res Comput Sci 3(1):83\u201397","journal-title":"Int J Adv Res Comput Sci"},{"key":"754_CR27","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver A (1986) Theory of linear and integer programming. Wiley, New York"},{"unstructured":"Uko LU, Lutz RJ, Weisel JA (2017) An application of linear programming in performance evaluation. Acad Educ Leadersh J","key":"754_CR28"},{"issue":"5","key":"754_CR29","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1007\/s10878-017-0140-2","volume":"34","author":"Z Wang","year":"2017","unstructured":"Wang Z, Nip K (2017) Bin packing under linear constraints. J Comb Optim 34(5):1198\u20131209","journal-title":"J Comb Optim"},{"key":"754_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, New York"},{"key":"754_CR31","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032701","volume-title":"Interior point algorithms: theory and analysis","author":"Y Ye","year":"1997","unstructured":"Ye Y (1997) Interior point algorithms: theory and analysis. Wiley-Interscience, New York"},{"doi-asserted-by":"crossref","unstructured":"Zhang S, Nip K, Wang Z (2018) Related machine scheduling with machine speeds satisfying linear constraints. In DK","key":"#cr-split#-754_CR32.1","DOI":"10.1007\/978-3-030-04651-4_21"},{"unstructured":"(ed) COCOA 2018 (The 12th annual international conference on combinatorial optimization and applications ). Volume 11346 of LNCS. Springer, Switzerland, pp 314-328","key":"#cr-split#-754_CR32.2"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00754-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00754-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00754-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T08:15:39Z","timestamp":1643444139000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00754-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,20]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["754"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00754-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,5,20]]},"assertion":[{"value":"4 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}