{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T17:37:06Z","timestamp":1790789826357,"version":"4.1.0"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job $J_j$ is associated with an interval, $I_j$, which consists of up to t segments, for some $t \\geq 1$, and a weight (profit), $w_j$; two jobs are in conflict if their intervals intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g., bandwidth in linear processor arrays), and computational biology\/geometry. The objective is to schedule a subset of nonconflicting jobs of maximum total weight.<\/jats:p>\n                  <jats:p>Our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of $t=1$ is an ordinary interval graph). We show that, for $t \\geq 2$, this problem is APX-hard, even for highly restricted instances. Our main result is a $2t$-approximation algorithm for general instances. This is based on a novel fractional version of the Local Ratio technique. One implication of this result is the first constant factor approximation for nonoverlapping alignment of genomic sequences. We also derive a bicriteria polynomial time approximation scheme for a restricted subclass of t-interval graphs.<\/jats:p>","DOI":"10.1137\/s0097539703437843","type":"journal-article","created":{"date-parts":[[2006,4,25]],"date-time":"2006-04-25T21:04:44Z","timestamp":1145999084000},"page":"1-15","source":"Crossref","is-referenced-by-count":90,"title":["Scheduling Split Intervals"],"prefix":"10.1137","volume":"36","author":[{"given":"R.","family":"Bar-Yehuda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. (S.)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H.","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"I.","family":"Shapira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","first-page":"405","volume":"30","author":"Akiyama J.","year":"1980","journal-title":"Math. Slovaca","ISSN":"https:\/\/id.crossref.org\/issn\/0139-9918","issn-type":"print"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00063-7"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Bar\u2010Yehuda, S. Even, A local\u2010ratio theorem for approximating the weighted vertex cover problem, North\u2010Holland Math. Stud., Vol. 109, North\u2010Holland, Amsterdam, 1985, 27\u20134587h:05158","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"R6","unstructured":"P. Basu, A. Narayanan, R. Krishnan, and T. D. C. Little,\n                      An implementation of dynamic service aggregation for interactive video delivery\n                      , in Proceedings of SPIE\u2014Multimedia Computing and Networking, San Jose, CA, 1998, pp. 110\u2013112."},{"key":"R7","first-page":"178","volume":"7","author":"Berman Piotr","year":"2000","journal-title":"Nordic J. Comput."},{"key":"R8","unstructured":"P. Berman, B. DasGupta, and S. Muthukrishnan,\n                      Simple approximation algorithm for nonoverlapping local alignments\n                      , in Proceedings of the 13th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2002, pp. 677\u2013678."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Piotr Berman, Toshihiro Fujito, On approximation properties of the independent set problem for degree 3 graphs, Lecture Notes in Comput. Sci., Vol. 955, Springer, Berlin, 1995, 449\u20134601465233","DOI":"10.1007\/3-540-60220-8_84"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Peter Brucker, Thomas Hilbig, Johann Hurink, A branch and bound algorithm for a single\u2010machine scheduling problem with positive and negative time\u2010lags, Proceedings of the Third International Conference on Graphs and Optimization, GO\u2010III (Leukerbad, 1998), Vol. 94, 1999, 77\u2013992000c:90026","DOI":"10.1016\/S0166-218X(99)00015-3"},{"key":"R11","unstructured":"M. Chleb\u00edk and J. Chleb\u00edkova,\n                      Approximation hardness of optimization problems in intersection graphs of d\u2010dimensional boxes\n                      , in Proceedings of the 16th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 267\u2013276."},{"key":"R12","unstructured":"A. Dan, P. Shahabuddin, and D. Sitaram,\n                      Channel Allocation under Batching and VCR Control in Movie\u2010On\u2010Demand Servers\n                      , IBM Research Report RC19588, IBM, Yorktown Heights, NY, 1994."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1287\/opre.44.5.777"},{"key":"R14","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0201013"},{"key":"R16","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin","year":"1980"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0601001"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90044-5"},{"key":"R19","unstructured":"Andr\u00e1s Gy\u00e1rf\u00e1s, Douglas West, Multitrack interval graphs, Proceedings of the Twenty\u2010sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), Vol. 109, 1995, 109\u201311696h:05161"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585870"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"L. A. Hall and D. B. Shmoys,\n                      Approximation algorithms for constrained scheduling problems\n                      , in Proceedings of the IEEE 30th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1989, pp. 134\u2013139.","DOI":"10.1109\/SFCS.1989.63468"},{"key":"R22","unstructured":"M. M. Halld\u00f3rsson, S. Rajagopalan, H. Shachnai, and A. Tomkins,\n                      Scheduling Multiple Resources\n                      , manuscript, 1999."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Magn\u00fas Halld\u00f3rsson, Kiyohito Yoshihara, Greedy approximations of independent sets in low degree graphs, Lecture Notes in Comput. Sci., Vol. 1004, Springer, Berlin, 1995, 152\u201316197c:05145","DOI":"10.1007\/BFb0015418"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Elad Hazan, Shmuel Safra, Oded Schwartz, On the complexity of approximating k\u2010dimensional matching, Lecture Notes in Comput. Sci., Vol. 2764, Springer, Berlin, 2003, 83\u2013972005c:68095","DOI":"10.1007\/978-3-540-45198-3_8"},{"key":"R25","unstructured":"G. Hoyle, Distance Learning on the Net, http:\/\/www.hoyle.com."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Klaus Jansen, Roberto Solis\u2010Oba, Maxim Sviridenko, Makespan minimization in job shops: a polynomial time approximation scheme, ACM, New York, 1999, 394\u20133991798060","DOI":"10.1145\/301250.301351"},{"key":"R28","unstructured":"David Karger, Cliff Stein, Joel Wein, Scheduling algorithms, CRC, Boca Raton, FL, 1999, 0\u20130, 35\u20101\u201335\u2010331797202"},{"key":"R29","unstructured":"Alexandr Kostochka, Douglas West, Every outerplanar graph is the union of two interval graphs, Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), Vol. 139, 1999, 5\u201381744225"},{"key":"R30","unstructured":"Nishit Kumar, Narsingh Deo, Multidimensional interval graphs, Proceedings of the Twenty\u2010fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1994), Vol. 102, 1994, 45\u20135696k:05162"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1000346"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Liane Lewin\u2010Eytan, Joseph Naor, Ariel Orda, Routing and admission control in networks with advance reservations, Lecture Notes in Comput. Sci., Vol. 2462, Springer, Berlin, 2002, 215\u20132282091828","DOI":"10.1007\/3-540-45753-4_19"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"C. Martin, P. S. Narayanan, B. Ozden, R. Rastogi, and A. Silberschatz,\n                      The Fellini multimedia storage server\n                      , in Multimedia Information Storage and Management, Kluwer Academic Publishers, Dordrecht, The Netharlands, 1996.","DOI":"10.1007\/978-1-4613-1431-8_5"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00041-8"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R37","unstructured":"A. H. G. Rinnooy Kan,\n                      Scheduling Problems\n                      , Martinus Nijhoff, The Hague, 1976."},{"key":"R38","doi-asserted-by":"crossref","unstructured":"D. Rotem,\n                      Analysis of disk arm movement for large sequential reads\n                      , in Proceedings of Principles of Database Systems (PODS), ACM, New York, 1992, pp. 47\u201354.","DOI":"10.1145\/137097.137108"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90050-3"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800270312"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979222676X"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190030302"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90127-6"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/BF02176235"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703437843","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:44Z","timestamp":1787336684000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703437843"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539703437843"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703437843","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}