{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T12:49:34Z","timestamp":1789994974597,"version":"4.0.1"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We introduce a new scheduling problem that is motivated by applications in the area of access and flow control in high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled \"as often as possible.\" There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. These conflicts are presented in the form of a conflict graph. We define parameters which quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters and present fair and efficient scheduling algorithms for the case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.<\/jats:p>","DOI":"10.1137\/s0097539795282092","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1168-1189","source":"Crossref","is-referenced-by-count":29,"title":["Guaranteeing Fair Service to Persistent Dependent Tasks"],"prefix":"10.1137","volume":"27","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alain","family":"Mayer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and M. Saks,\n                      A dining philosophers algorithm with polynomial response time\n                      , in Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 65\u201375.","DOI":"10.1109\/FSCS.1990.89525"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900032"},{"key":"R3","unstructured":"D. Bertsekas and R. Gallager,\n                      Data Networks\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1987."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"J. Bar\u2010Ilan and D. Peleg,\n                      Distributed resource allocation algorithms\n                      , in Proc. 6th International Workshop on Distributed Algorithms, 1992, pp. 277\u2013291.","DOI":"10.1007\/3-540-56188-9_19"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/49.245907"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/1780.1804"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/26.212370"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Choy and A. Singh,\n                      Efficient fault tolerant algorithms for resource allocation in distributed system\n                      , in Proc. 24th ACM Symp. on Theory of Computing (1992), pp. 593\u2013602.","DOI":"10.1145\/129712.129770"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289519"},{"key":"R10","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R11","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin","year":"1980"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/26.58761"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1095081"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90011-P"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.37236\/1193"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis,\n                      On the hardness of approximating minimization problems\n                      , in Proc. 25th ACM Symp. on Theory of Computing, 1993, pp. 286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"N. Lynch,\n                      Fast allocation of nearby resources in a distributed system\n                      , in Proc. 12th ACM Symp. on Theory of Computing, 1980, pp. 70\u201381.","DOI":"10.1145\/800141.804654"},{"key":"R20","unstructured":"A. Mayer, Y. Ofek, and M. Yung,\n                      Local scheduling with partial state information for approximate max\u2010min fair rates\n                      , in Proc. IEEE INFOCOM\u201996, 1996."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1971.39.535"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795282092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:11Z","timestamp":1787335931000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795282092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795282092"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795282092","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}