{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297380,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"Abstract<\/jats:title>We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by d<\/jats:italic>. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding a minimum-weight vertex cover in a d<\/jats:italic>-partite hypergraph. Next, we study the natural LP relaxation, which can be solved in polynomial time for fixed d<\/jats:italic> and\u2014for time-cost tradeoff instances\u2014up to an arbitrarily small error in general. Improving on prior work of Lov\u00e1sz and of Aharoni, Holzman and Krivelevich, we describe a deterministic algorithm with approximation ratio slightly less than $$\\frac{d}{2}$$<\/jats:tex-math>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for minimum-weight vertex cover in d<\/jats:italic>-partite hypergraphs for fixed d<\/jats:italic> and given d<\/jats:italic>-partition. This is tight and yields also a $$\\frac{d}{2}$$<\/jats:tex-math>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm for general time-cost tradeoff instances, even if d<\/jats:italic> is not fixed. We also study the inapproximability and show that no better approximation ratio than $$\\frac{d+2}{4}$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n 4<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is possible, assuming the Unique Games Conjecture and $$\\text {P}\\ne \\text {NP}$$<\/jats:tex-math>\n \n P<\/mml:mtext>\n \u2260<\/mml:mo>\n NP<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This strengthens a result of Svensson [21], who showed that under the same assumptions no constant-factor approximation algorithm exists for general time-cost tradeoff instances (of unbounded depth). Previously, only APX-hardness was known for bounded depth.\n<\/jats:p>","DOI":"10.1007\/s10107-022-01777-9","type":"journal-article","created":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T11:04:41Z","timestamp":1644577481000},"page":"529-547","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the discrete time-cost tradeoff problem with bounded depth"],"prefix":"10.1007","volume":"197","author":[{"given":"Siad","family":"Daboul","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2188-1559","authenticated-orcid":false,"given":"Stephan","family":"Held","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,11]]},"reference":[{"issue":"2","key":"1777_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF01844843","volume":"16","author":"R Aharoni","year":"1996","unstructured":"Aharoni, R., Holzman, R., Krivelevich, M.: On a theorem of Lov\u00e1sz on covers in $$r$$-partite hypergraphs. Combinatorica 16(2), 149\u2013174 (1996)","journal-title":"Combinatorica"},{"issue":"1\u20132","key":"1777_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1777_CR3","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"12","key":"1777_CR4","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum $$k$$-path vertex cover. Discret. Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"1777_CR5","first-page":"68","volume":"23","author":"S Daboul","year":"2018","unstructured":"Daboul, S., Held, S., Vygen, J., Wittke, S.: An approximation algorithm for threshold voltage optimization. Trans. Des. Autom. Electron. Syst. 23(6), 68 (2018)","journal-title":"Trans. Des. Autom. Electron. Syst."},{"issue":"2","key":"1777_CR6","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1287\/opre.45.2.302","volume":"45","author":"P De","year":"1997","unstructured":"De, P., Dunne, E.J., Ghosh, J.B., Wells, C.E.: Complexity of the discrete time-cost tradeoff problem for project networks. Oper. Res. 45(2), 302\u2013306 (1997)","journal-title":"Oper. Res."},{"issue":"5","key":"1777_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/S0167-6377(01)00102-X","volume":"29","author":"VG De\u01d0neko","year":"2001","unstructured":"De\u01d0neko, V.G., Woeginger, G.J.: Hardness of approximation of the discrete time-cost tradeoff problem. Oper. Res. Lett. 29(5), 207\u2013210 (2001)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1777_CR8","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.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math."},{"issue":"3","key":"1777_CR9","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0021-9800(70)80083-7","volume":"8","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J., Fulkerson, D.R.: Bottleneck extrema. J. Combin. Theory 8(3), 299\u2013306 (1970)","journal-title":"J. Combin. Theory"},{"key":"1777_CR10","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248\u2013264 (1972)","journal-title":"J. ACM"},{"issue":"2","key":"1777_CR11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00236-004-0150-2","volume":"41","author":"A Grigoriev","year":"2004","unstructured":"Grigoriev, A., Woeginger, G.J.: Project scheduling with irregular costs: complexity, approximability, and algorithms. Acta Informatica 41(2), 83\u201397 (2004)","journal-title":"Acta Informatica"},{"key":"1777_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"1777_CR13","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1137\/130919416","volume":"29","author":"V Guruswami","year":"2015","unstructured":"Guruswami, V., Sachdeva, S., Saket, R.: Inapproximability of minimum vertex cover on $$k$$-uniform $$k$$-partite hypergraphs. SIAM J. Discret. Math. 29(1), 36\u201358 (2015)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"1777_CR14","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1215\/S0012-7094-58-02537-7","volume":"25","author":"JR Isbell","year":"1958","unstructured":"Isbell, J.R.: A class of simple games. Duke Math. J. 25(3), 423\u2013439 (1958)","journal-title":"Duke Math. J."},{"key":"1777_CR15","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"1777_CR16","doi-asserted-by":"crossref","unstructured":"Kelley, J.E., Walker, M.R.: Critical-path planning and scheduling. In: Proceedings of the AIEE-ACM \u201959, pp. 160\u2013173 (1959)","DOI":"10.1145\/1460299.1460318"},{"issue":"3","key":"1777_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.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"1777_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-018-1255-7","volume":"177","author":"E Lee","year":"2019","unstructured":"Lee, E.: Partitioning a graph into small pieces with applications to path transversal. Math. Program. 177, 1\u201319 (2019)","journal-title":"Math. Program."},{"key":"1777_CR19","first-page":"209","volume":"26","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On minmax theorems of combinatorics, Doctoral Thesis (in Hungarian). Mathematikai Lapok 26, 209\u2013264 (1975)","journal-title":"Mathematikai Lapok"},{"issue":"4","key":"1777_CR20","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1287\/moor.23.4.909","volume":"23","author":"M Skutella","year":"1998","unstructured":"Skutella, M.: Approximation algorithms for the discrete time-cost tradeoff problem. Math. Oper. Res. 23(4), 909\u2013929 (1998)","journal-title":"Math. Oper. Res."},{"issue":"24","key":"1777_CR21","doi-asserted-by":"publisher","first-page":"759","DOI":"10.4086\/toc.2013.v009a024","volume":"9","author":"O Svensson","year":"2013","unstructured":"Svensson, O.: Hardness of vertex deletion and project scheduling. Theory Comput. 9(24), 759\u2013781 (2013)","journal-title":"Theory Comput."},{"issue":"2","key":"1777_CR22","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/net.3230010206","volume":"1","author":"N Tomizawa","year":"1971","unstructured":"Tomizawa, N.: On some techniques useful for solution of transportation network problems. Networks 1(2), 173\u2013194 (1971)","journal-title":"Networks"},{"issue":"50","key":"1777_CR23","doi-asserted-by":"publisher","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"J Tu","year":"2011","unstructured":"Tu, J., Zhou, W.: A primal-dual approximation algorithm for the vertex cover P3 problem. Theoret. Comput. Sci. 412(50), 7044\u20137048 (2011)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01777-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01777-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01777-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:18:10Z","timestamp":1675703890000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01777-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1777"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01777-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,2,11]]},"assertion":[{"value":"20 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}