{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T12:39:56Z","timestamp":1775997596881,"version":"3.50.1"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006919","name":"Massachusetts Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006919","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,11]]},"abstract":"Abstract<\/jats:title>The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost $$f(\\cdot )$$<\/jats:tex-math>\n \n f<\/mml:mi>\n (<\/mml:mo>\n \u00b7<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> due to an ordering $$\\sigma $$<\/jats:tex-math>\n \u03c3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the items (say [n<\/jats:italic>]), i.e., $$\\min _{\\sigma } \\sum _{i\\in [n]} f(E_{i,\\sigma })$$<\/jats:tex-math>\n \n \n min<\/mml:mo>\n \u03c3<\/mml:mi>\n <\/mml:msub>\n \n \u2211<\/mml:mo>\n \n i<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n f<\/mml:mi>\n \n (<\/mml:mo>\n \n E<\/mml:mi>\n \n i<\/mml:mi>\n ,<\/mml:mo>\n \u03c3<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$E_{i,\\sigma }$$<\/jats:tex-math>\n \n E<\/mml:mi>\n \n i<\/mml:mi>\n ,<\/mml:mo>\n \u03c3<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the set of items mapped by $$\\sigma $$<\/jats:tex-math>\n \u03c3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to indices [i<\/jats:italic>]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lov\u00e1sz extension of submodular functions. We show a $$(2-\\frac{1+\\ell _{f}}{1+|E|})$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n \n \n 1<\/mml:mn>\n +<\/mml:mo>\n \n \u2113<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n |<\/mml:mo>\n E<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for monotone submodular MLOP where $$\\ell _{f}=\\frac{f(E)}{\\max _{x\\in E}f(\\{x\\})}$$<\/jats:tex-math>\n \n \n \u2113<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n \n \n f<\/mml:mi>\n (<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \n max<\/mml:mo>\n \n x<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n f<\/mml:mi>\n \n (<\/mml:mo>\n \n {<\/mml:mo>\n x<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfies $$1 \\le \\ell _f \\le |E|$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n \u2264<\/mml:mo>\n \n \u2113<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \n |<\/mml:mo>\n E<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our theory provides new approximation bounds for special cases of the problem, in particular a $$(2-\\frac{1+r(E)}{1+|E|})$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 2<\/mml:mn>\n -<\/mml:mo>\n \n \n 1<\/mml:mn>\n +<\/mml:mo>\n r<\/mml:mi>\n (<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n |<\/mml:mo>\n E<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for the matroid MLOP, where $$f = r$$<\/jats:tex-math>\n \n f<\/mml:mi>\n =<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the rank function of a matroid. We further show that minimum latency vertex cover is $$\\frac{4}{3}$$<\/jats:tex-math>\n \n 4<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.<\/jats:p>","DOI":"10.1007\/s10107-023-02038-z","type":"journal-article","created":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T15:02:36Z","timestamp":1702566156000},"page":"277-318","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hardness and approximation of submodular minimum linear ordering problems"],"prefix":"10.1007","volume":"208","author":[{"given":"Majid","family":"Farhadi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9566-3856","authenticated-orcid":false,"given":"Swati","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengding","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael C.","family":"Wigal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,14]]},"reference":[{"key":"2038_CR1","doi-asserted-by":"crossref","unstructured":"Iwata, S., Tetali, P., Tripathi, P.: Approximating minimum linear ordering problems. In: APPROX, pp. 206\u2013217 (2012)","DOI":"10.1007\/978-3-642-32512-0_18"},{"issue":"4","key":"2038_CR2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1017\/S0963548302005175","volume":"11","author":"J Oxley","year":"2002","unstructured":"Oxley, J., Welsh, D.: Chromatic, flow and reliability polynomials: the complexity of their coefficients. Comb. Probab. Comput. 11(4), 403\u2013426 (2002)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"2038_CR3","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1090\/S0002-9947-1959-0101527-3","volume":"90","author":"WT Tutte","year":"1959","unstructured":"Tutte, W.T.: Matroids and graphs. Trans. Am. Math. Soc. 90(3), 527\u2013552 (1959)","journal-title":"Trans. Am. Math. Soc."},{"key":"2038_CR4","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, Oxford (2006)"},{"issue":"1\u20132","key":"2038_CR5","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C Chekuri","year":"1999","unstructured":"Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discret. Appl. Math. 98(1\u20132), 29\u201338 (1999)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"2038_CR6","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"LA Hall","year":"1997","unstructured":"Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22(3), 513\u2013544 (1997)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"2038_CR7","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1287\/opre.51.6.981.24912","volume":"51","author":"F Margot","year":"2003","unstructured":"Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Oper. Res. 51(6), 981\u2013992 (2003)","journal-title":"Oper. Res."},{"issue":"4","key":"2038_CR8","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1287\/moor.1110.0512","volume":"36","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Mutsanas, N., Svensson, O.: On the approximability of single-machine scheduling with precedence constraints. Math. Oper. Res. 36(4), 653\u2013669 (2011)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"2038_CR9","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. (CSUR) 34(3), 313\u2013356 (2002)","journal-title":"ACM Comput. Surv. (CSUR)"},{"issue":"105","key":"2038_CR10","first-page":"177","volume":"3","author":"J Petit","year":"2013","unstructured":"Petit, J.: Addenda to the survey of layout problems. Bull. EATCS 3(105), 177\u2013201 (2013)","journal-title":"Bull. EATCS"},{"key":"2038_CR11","first-page":"157","volume":"7","author":"SL Bezrukov","year":"1999","unstructured":"Bezrukov, S.L.: Edge isoperimetric problems on graphs. Graph Theory Comb. Biol. 7, 157\u2013197 (1999)","journal-title":"Graph Theory Comb. Biol."},{"issue":"2","key":"2038_CR12","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S","volume":"31","author":"Y-L Lai","year":"1999","unstructured":"Lai, Y.-L., Williams, K.: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31(2), 75\u201394 (1999)","journal-title":"J. Graph Theory"},{"issue":"3","key":"2038_CR13","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1109\/TCT.1969.1082966","volume":"16","author":"G Kishi","year":"1969","unstructured":"Kishi, G., Kajitani, Y.: Maximally distant trees and principal partition of a linear graph. IEEE Trans. Circuit Theory 16(3), 323\u2013330 (1969)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"2038_CR14","doi-asserted-by":"crossref","unstructured":"Fujishige, S.: Theory of Principal Partitions Revisited, pp. 127\u2013162. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-540-76796-1_7","DOI":"10.1007\/978-3-540-76796-1_7"},{"issue":"12","key":"2038_CR15","first-page":"1769","volume":"32","author":"N Pisaruk","year":"1992","unstructured":"Pisaruk, N.: The boundaries of submodular functions. Comput. Math. Math. Phys. 32(12), 1769\u20131783 (1992)","journal-title":"Comput. Math. Math. Phys."},{"issue":"4","key":"2038_CR16","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1287\/moor.2018.0978","volume":"44","author":"R Fokkink","year":"2019","unstructured":"Fokkink, R., Lidbetter, T., V\u00e9gh, L.A.: On submodular search and machine scheduling. Math. Oper. Res. 44(4), 1431\u20131449 (2019)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2038_CR17","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Ind. Appl. Math. 12(1), 131\u2013135 (1964)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"2038_CR18","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1137\/0208002","volume":"8","author":"Y Shiloach","year":"1979","unstructured":"Shiloach, Y.: A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 8(1), 15\u201318 (1979). (02)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2038_CR19","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0898-1221(84)90085-3","volume":"10","author":"F-RK Chung","year":"1984","unstructured":"Chung, F.-R.K.: On optimal linear arrangements of trees. Comput. Math. Appl. 10(1), 43\u201360 (1984)","journal-title":"Comput. Math. Appl."},{"key":"2038_CR20","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"issue":"1","key":"2038_CR21","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.ipl.2006.07.009","volume":"101","author":"U Feige","year":"2007","unstructured":"Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1), 26\u201329 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"2038_CR22","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s00453-008-9191-1","volume":"56","author":"M Charikar","year":"2010","unstructured":"Charikar, M., Hajiaghayi, M.T., Karloff, H., Rao, S.: $$\\ell _2^2$$ spreading metrics for vertex ordering problems. Algorithmica 56(4), 577\u2013604 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"2038_CR23","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"2038_CR24","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1137\/080729256","volume":"40","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput. 40(2), 567\u2013596 (2011)","journal-title":"SIAM J. Comput."},{"key":"2038_CR25","doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I., Yin, X.: Multiple intents re-ranking. In: Symposium on Theory of Computing, STOC, pp. 669\u2013678 (2009)","DOI":"10.1145\/1536414.1536505"},{"issue":"4","key":"2038_CR26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U Feige","year":"2004","unstructured":"Feige, U., Lov\u00e1sz, L., Tetali, P.: Approximating min sum set cover. Algorithmica 40(4), 219\u2013234 (2004)","journal-title":"Algorithmica"},{"key":"2038_CR27","doi-asserted-by":"crossref","unstructured":"Hassin, R., Levin, A.: An approximation algorithm for the minimum latency set cover problem. In: European Symposium on Algorithms, ESA, pp. 726\u2013733 (2005)","DOI":"10.1007\/11561071_64"},{"key":"2038_CR28","doi-asserted-by":"crossref","unstructured":"D\u00edaz, J., Gibbons, A., Paterson, M., Toran, J.: The minsumcut problem. In: Workshop on Algorithms and Data Structures. Springer, Berlin, pp. 65\u201379 (1991)","DOI":"10.1007\/BFb0028251"},{"issue":"1","key":"2038_CR29","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF02006264","volume":"10","author":"Y Lin","year":"1994","unstructured":"Lin, Y., Yuan, J.: Profile minimization problem for matrices and graphs. Acta Math. Appl. Sin. 10(1), 107\u2013112 (1994)","journal-title":"Acta Math. Appl. Sin."},{"key":"2038_CR30","unstructured":"Even, S., Shiloah, Y.: NP-completeness of several arrangement problems. Technical Report; Israel Institute of Technology, Department of Computer Science, vol.\u00a043 (1975)"},{"key":"2038_CR31","doi-asserted-by":"crossref","unstructured":"Bansal, N., Batra, J., Farhadi, M., Tetali, P.: Improved approximations for min sum vertex cover and generalized min sum set cover. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 998\u20131005. SIAM, Philadelphia (2021)","DOI":"10.1137\/1.9781611976465.62"},{"issue":"2","key":"2038_CR32","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1137\/S0097539702413197","volume":"34","author":"S Rao","year":"2005","unstructured":"Rao, S., Richa, A.W.: New approximation techniques for some linear ordering problems. SIAM J. Comput. 34(2), 388\u2013404 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3\u20134","key":"2038_CR33","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S Burer","year":"2001","unstructured":"Burer, S., Monteiro, R.D.: A projected gradient algorithm for solving the maxcut SDP relaxation. Optim. Methods Softw. 15(3\u20134), 175\u2013200 (2001)","journal-title":"Optim. Methods Softw."},{"key":"2038_CR34","unstructured":"Barenholz, U., Feige, U., Peleg, D., et al.: Improved approximation for min-sum vertex cover, MCS06-07. Technical Report, Computer Science and Applied Mathematics (2006)"},{"key":"2038_CR35","unstructured":"Stankovi\u0107, A.: Some results on approximability of minimum sum vertex cover. arXiv preprint arXiv:2212.11882 (2022)"},{"key":"2038_CR36","doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: Symposium on Discrete Algorithms, SODA, pp. 1539\u20131545 (2010)","DOI":"10.1137\/1.9781611973075.125"},{"issue":"6","key":"2038_CR37","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/j.orl.2011.08.002","volume":"39","author":"M Skutella","year":"2011","unstructured":"Skutella, M., Williamson, D.P.: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6), 433\u2013436 (2011)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"2038_CR38","first-page":"377","volume":"145","author":"S Im","year":"2014","unstructured":"Im, S., Sviridenko, M., van der Zwaan, R.: Preemptive and non-preemptive generalized min sum set cover. Math. Program. 145(1\u20132), 377\u2013401 (2014)","journal-title":"Math. Program."},{"key":"2038_CR39","doi-asserted-by":"crossref","unstructured":"Tsaparas, P., Ntoulas, A., Terzi, E.: Selecting a comprehensive set of reviews. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 168\u2013176 (2011)","DOI":"10.1145\/2020408.2020440"},{"key":"2038_CR40","doi-asserted-by":"crossref","unstructured":"Luo, W., Chakraborty, N., Sycara, K.: Distributed dynamic priority assignment and motion planning for multiple mobile robots with kinodynamic constraints. In: American Control Conference (ACC), pp. 148\u2013154. IEEE (2016)","DOI":"10.1109\/ACC.2016.7524907"},{"issue":"4","key":"2038_CR41","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1287\/moor.2018.0978","volume":"44","author":"R Fokkink","year":"2019","unstructured":"Fokkink, R., Lidbetter, T., V\u00e9gh, L.A.: On submodular search and machine scheduling. Math. Oper. Res. 44(4), 1431\u20131449 (2019)","journal-title":"Math. Oper. Res."},{"key":"2038_CR42","unstructured":"Happach, F.: Min-sum set cover, or-scheduling, and related problems. Ph.D. dissertation, Technische Universit\u00e4t M\u00fcnchen (2020)"},{"key":"2038_CR43","unstructured":"Happach, F., Hellerstein, L., Lidbetter, T.: A general framework for approximating min sum ordering problems. arXiv preprint arXiv:2004.05954 (2020)"},{"key":"2038_CR44","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"key":"2038_CR45","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0024-3795(91)90070-D","volume":"144","author":"H Narayanan","year":"1991","unstructured":"Narayanan, H.: The principal lattice of partitions of a submodular function. Linear Algebra Appl. 144, 179\u2013216 (1991)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"2038_CR46","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1137\/S0895480103428338","volume":"19","author":"L Khachiyan","year":"2005","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On the complexity of some enumeration problems for matroids. SIAM J. Discrete Math. 19(4), 966\u2013984 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"2038_CR47","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Foundations of Computer Science, FOCS, pp. 453\u2013462 (2009)","DOI":"10.1109\/FOCS.2009.23"},{"issue":"4","key":"2038_CR48","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"JR Correa","year":"2005","unstructured":"Correa, J.R., Schulz, A.S.: Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4), 1005\u20131021 (2005)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"2038_CR49","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/s00453-008-9251-6","volume":"53","author":"C Amb\u00fchl","year":"2009","unstructured":"Amb\u00fchl, C., Mastrolilli, M.: Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica 53(4), 488\u2013503 (2009)","journal-title":"Algorithmica"},{"issue":"3","key":"2038_CR50","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"2038_CR51","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2038_CR52","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF00814406","volume":"9","author":"GR Brightwell","year":"1992","unstructured":"Brightwell, G.R., Scheinerman, E.R.: Fractional dimension of partial orders. Order 9(2), 139\u2013158 (1992)","journal-title":"Order"},{"key":"2038_CR53","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative Methods in Combinatorial Optimization","author":"LC Lau","year":"2011","unstructured":"Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization, vol. 46. Cambridge University Press, Cambridge (2011)"},{"issue":"01","key":"2038_CR54","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/S0129054103001637","volume":"14","author":"K Nakano","year":"2003","unstructured":"Nakano, K.: Linear layout of generalized hypercubes. Int. J. Found. Comput. Sci. 14(01), 137\u2013156 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"70","key":"2038_CR55","first-page":"21","volume":"1","author":"D Muradyan","year":"1980","unstructured":"Muradyan, D., Piliposjan, T.: Minimal numberings of vertices of a rectangular lattice. Akad. Nauk. Armjan. SRR 1(70), 21\u201327 (1980). (in Russian)","journal-title":"Akad. Nauk. Armjan. SRR"},{"key":"2038_CR56","first-page":"18","volume":"2","author":"D Muradyan","year":"1980","unstructured":"Muradyan, D., Piliposyan, T.: The problem of finding the length and width of the complete p-partite graph. Fluchen. Zapiski Erevan. Gosunivers 2, 18\u201326 (1980). (in Russian)","journal-title":"Fluchen. Zapiski Erevan. Gosunivers"},{"key":"2038_CR57","first-page":"37","volume":"11","author":"L Harper","year":"1970","unstructured":"Harper, L.: Chassis layout and isoperimetric problems. Jet Propuls. Lab. SPS 11, 37\u201366 (1970)","journal-title":"Jet Propuls. Lab. SPS"},{"key":"2038_CR58","unstructured":"Nagano, K., Kawahara, Y., Aihara, K.: Size-constrained submodular minimization through minimum norm base. In: Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 977\u2013984 (2011)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02038-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02038-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02038-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T16:07:07Z","timestamp":1729008427000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02038-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,14]]},"references-count":58,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["2038"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02038-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,14]]},"assertion":[{"value":"23 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interest"}}]}}