{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:07:04Z","timestamp":1674817624874},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,7]]},"abstract":"\n The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over\n n<\/jats:italic>\n letters where each letter is distributed as \u201cevenly\u201d as possible and appears with a given rate? The second objective of the paper is to use this construction in the framework of optimal routing in queuing networks. We show under rather general assumptions that the optimal deterministic routing in stochastic event graphs is such a sequence.\n <\/jats:p>","DOI":"10.1145\/347476.347482","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"752-775","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Balanced sequences and optimal routing"],"prefix":"10.1145","volume":"47","author":[{"given":"Eitan","family":"Altman","sequence":"first","affiliation":[{"name":"INRIA, Sophia Antipolis, France"}]},{"given":"Bruno","family":"Gaujal","sequence":"additional","affiliation":[{"name":"LORIA, Villers-des-Nancy, France"}]},{"given":"Arie","family":"Hordijk","sequence":"additional","affiliation":[{"name":"Leiden Univ., Leiden, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2000,7]]},"reference":[{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"ALTMAN E. AND STIDHAM S. 1995. Optimality of monotonic policies for two-action Markovian decision processes with applications to control of queues with delayed information. Queuing Syst.: ALTMAN E. AND STIDHAM S. 1995. Optimality of monotonic policies for two-action Markovian decision processes with applications to control of queues with delayed information. Queuing Syst.:","DOI":"10.1007\/BF01149165"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.24033\/bsmf.2220","article-title":"Complexity of sequences defined by billiards in the cube","volume":"122","author":"ARNOUX P.","year":"1994","unstructured":"ARNOUX , P. , MAUDUIT , C. , SHIOKAWA , I. , AND TAMURA , J. 1994 . Complexity of sequences defined by billiards in the cube . BSMF (Bull. Soc. Math. France) 122 , 1 - 12 . ARNOUX, P., MAUDUIT, C., SHIOKAWA, I., AND TAMURA, J. 1994. Complexity of sequences defined by billiards in the cube. BSMF (Bull. Soc. Math. France) 122, 1-12.","journal-title":"BSMF (Bull. Soc. Math. France)"},{"issue":"12","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1751","DOI":"10.1109\/9.545714","article-title":"Free choice nets, an algebraic approach","volume":"41","author":"BACCELLI F.","year":"1996","unstructured":"BACCELLI , F. , FOSS , S. , AND GAUJAL , B. 1996 . Free choice nets, an algebraic approach . IEEE Trans. Autom. Cont. 41 , 12 , 1751 - 1778 . BACCELLI, F., FOSS, S., AND GAUJAL, B. 1996. Free choice nets, an algebraic approach. IEEE Trans. Autom. Cont. 41, 12, 1751-1778.","journal-title":"IEEE Trans. Autom. Cont."},{"key":"e_1_2_1_6_1","unstructured":"BACCELLI F. GOHEN G. OLSDER G. J. AND QUADRAT J.-P. 1992. Synchronization and Linearity. Wiley New York. BACCELLI F. GOHEN G. OLSDER G. J. AND QUADRAT J.-P. 1992. Synchronization and Linearity. Wiley New York."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"BAR-NOY A.","year":"1998","unstructured":"BAR-NOY , A. , BHATIA , R. , NAOR , J. , AND SCHIEBER , B. 1998 . Minimizing service and operation costs of periodic scheduling . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York. BAR-NOY, A., BHATIA, R., NAOR, J., AND SCHIEBER, B. 1998. Minimizing service and operation costs of periodic scheduling. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF02099463","article-title":"Complexity of trajectories in rectangular billiards","volume":"175","author":"BARYSHNIKOV Y.","year":"1995","unstructured":"BARYSHNIKOV , Y. 1995 . Complexity of trajectories in rectangular billiards . Commun. Math. Phy. 175 , 43 - 56 . BARYSHNIKOV, Y. 1995. Complexity of trajectories in rectangular billiards. Commun. Math. Phy. 175, 43-56.","journal-title":"Commun. Math. Phy."},{"key":"e_1_2_1_9_1","first-page":"175","article-title":"Morphismes de","volume":"1","author":"BERSTEL J.","year":"1994","unstructured":"BERSTEL , J. , AND St~t~ BOLD , P. 1994 . Morphismes de Sturm. Bull. Belg. Math. Soc. 1 , 175 - 189 . BERSTEL, J., AND St~t~BOLD, P. 1994. Morphismes de Sturm. Bull. Belg. Math. Soc. 1, 175-189.","journal-title":"Sturm. Bull. Belg. Math. Soc."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1109\/5.21080","article-title":"Distributed routing for load balancing","author":"BOEL R. K.","year":"1989","unstructured":"BOEL , R. K. , AND VAN SCHUPPEN , J.H. 1989 . Distributed routing for load balancing . Proc. IEEE , 210 - 221 . BOEL, R. K., AND VAN SCHUPPEN, J.H. 1989. Distributed routing for load balancing. Proc. IEEE, 210-221.","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 29th Conference on Decision and Control.","author":"CHANG C. S.","year":"1990","unstructured":"CHANG , C. S. , CHAO , X. , AND PINEDO , M. 1990 . A note on queues with Bernoulli routing . In Proceedings of the 29th Conference on Decision and Control. CHANG, C. S., CHAO, X., AND PINEDO, M. 1990. A note on queues with Bernoulli routing. In Proceedings of the 29th Conference on Decision and Control."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90292-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/0097-3165(73)90059-9","article-title":"Complementary and exactly covering sequences","volume":"14","author":"FRAENKEL A.","year":"1973","unstructured":"FRAENKEL , A. 1973 . Complementary and exactly covering sequences . J. Combinat. Theory 14 , 8 - 20 . FRAENKEL, A. 1973. Complementary and exactly covering sequences. J. Combinat. Theory 14, 8 -20.","journal-title":"J. Combinat. Theory"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008256825451"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0097-3165(73)90084-8","article-title":"Covering the positive integers by disjoint sets of the form {{nc~ + \/3} :n = 1, 2, ..}","volume":"15","author":"GRAHAM R.","year":"1973","unstructured":"GRAHAM , R. 1973 . Covering the positive integers by disjoint sets of the form {{nc~ + \/3} :n = 1, 2, ..} . J. Combin. Theory 15 , 354 - 358 . GRAHAM, R. 1973. Covering the positive integers by disjoint sets of the form {{nc~ + \/3} :n = 1, 2, ..}. J. Combin. Theory 15, 354-358.","journal-title":"J. Combin. Theory"},{"issue":"4","key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1287\/moor.10.4.543","article-title":"Extremal splittings of point processes","volume":"10","author":"HAJEK B.","year":"1985","unstructured":"HAJEK , B. 1985 . Extremal splittings of point processes . Math. Oper. Res. 10 , 4 , 543 - 556 . HAJEK, B. 1985. Extremal splittings of point processes. Math. Oper. Res. 10, 4, 543-556.","journal-title":"Math. Oper. Res."},{"key":"e_1_2_1_17_1","first-page":"90","article-title":"A survey of research relevant to virtual circuit routing in telecommunication networks","author":"HARIHARAN R.","year":"1990","unstructured":"HARIHARAN , R. , HULHARNI , g. G. , AND STIDHAM , S. 1990 . A survey of research relevant to virtual circuit routing in telecommunication networks . Tech. Rep. WC\/OR\/TR 90 - 13 . Univ. N. Carolina at Chapel Hill, Chapel Hill, N.C. HARIHARAN, R., HULHARNI, g. G., AND STIDHAM, S. 1990. A survey of research relevant to virtual circuit routing in telecommunication networks. Tech. Rep. WC\/OR\/TR 90-13. Univ. N. Carolina at Chapel Hill, Chapel Hill, N.C.","journal-title":"Tech. Rep. WC\/OR\/TR"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1017\/S0269964800002692","article-title":"On the assignment of customers to parallel queues","volume":"6","author":"HORDIJK A.","year":"1992","unstructured":"HORDIJK , A. , AND KOOLE , G. 1992 . On the assignment of customers to parallel queues . Probab. Eng. Inf. Sci. 6 , 495 - 511 . HORDIJK, A., AND KOOLE, G. 1992. On the assignment of customers to parallel queues. Probab. Eng. Inf. Sci. 6, 495-511.","journal-title":"Probab. Eng. Inf. Sci."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1017\/S0269964800003508","article-title":"Analysis of a customer assignment model with no state information","volume":"8","author":"HORDIJK A.","year":"1994","unstructured":"HORDIJK , A. , KOOLE , G. , AND LOEVE , A. 1994 . Analysis of a customer assignment model with no state information . Probab. Eng. Inf. Sci. 8 , 419 - 429 . HORDIJK, A., KOOLE, G., AND LOEVE, A. 1994. Analysis of a customer assignment model with no state information. Probab. Eng. Inf. Sci. 8, 419-429.","journal-title":"Probab. Eng. Inf. Sci."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00208-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.21.2.469"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.4.563"},{"key":"e_1_2_1_24_1","unstructured":"LOTHAIRE M. 1991. Mots chapter Trac6 de droites fractions continues et morphismes itdrds (J. Berstel). Hermes. LOTHAIRE M. 1991. Mots chapter Trac6 de droites fractions continues et morphismes itdrds (J. Berstel). Hermes."},{"key":"e_1_2_1_25_1","unstructured":"MORIKAWA R. 1985-1993. Disjoint sequences generated by the bracket function i-vi. Tech. Reps. 26(1985) 28(1988) 30(1989) 32(1992) 34(1993). Bulletin of the Faculty of Liberal Arts Nagasaki Univ. Nagasaki Japan. MORIKAWA R. 1985-1993. Disjoint sequences generated by the bracket function i-vi. Tech. Reps. 26(1985) 28(1988) 30(1989) 32(1992) 34(1993). Bulletin of the Faculty of Liberal Arts Nagasaki Univ. Nagasaki Japan."},{"key":"e_1_2_1_26_1","unstructured":"MORIKAWA R. 1982-1995. On eventually covering families generated by the bracket function i-v. Tech. Reps. 23(1982) 24(1983) 25(1984) 26(1985) 25(1985) 36(1995). Bulletin of the Faculty of Liberal Arts Nagasaki Univ. Nagasaki Japan. MORIKAWA R. 1982-1995. On eventually covering families generated by the bracket function i-v. Tech. Reps. 23(1982) 24(1983) 25(1984) 26(1985) 25(1985) 36(1995). Bulletin of the Faculty of Liberal Arts Nagasaki Univ. Nagasaki Japan."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.2307\/2371431","article-title":"Symbolic dynamics II-Sturmian trajectories","volume":"62","author":"MORSE M.","year":"1940","unstructured":"MORSE , M. , AND HEDLUND , G. A. 1940 . Symbolic dynamics II-Sturmian trajectories . Amer. J. Math. 62 , 287 - 306 . MORSE, M., AND HEDLUND, G. A. 1940. Symbolic dynamics II-Sturmian trajectories. Amer. J. Math. 62, 287-306.","journal-title":"Amer. J. Math."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01350330","article-title":"Roots of unity and covering sets","volume":"191","author":"NEWMAN M.","year":"1971","unstructured":"NEWMAN , M. 1971 . Roots of unity and covering sets . Math. Ann. 191 , 279 - 282 . NEWMAN, M. 1971. Roots of unity and covering sets. Math. Ann. 191,279-282.","journal-title":"Math. Ann."},{"key":"e_1_2_1_29_1","volume-title":"Introduction to Ergodic Theory","author":"SINAI Y.G.","unstructured":"SINAI , Y.G. 1976. Introduction to Ergodic Theory . Princeton University Press , Princeton, N.J. SINAI, Y.G. 1976. Introduction to Ergodic Theory. Princeton University Press, Princeton, N.J."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/0019-3577(96)83728-1","article-title":"On complementary triples of Sturmian sequences","author":"TIJDEMAN R.","year":"1996","unstructured":"TIJDEMAN , R. 1996 . On complementary triples of Sturmian sequences . Indag. Math. 419 - 424 . TIJDEMAN, R. 1996. On complementary triples of Sturmian sequences. Indag. Math. 419-424.","journal-title":"Indag. Math."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0019-3577(97)87570-2","article-title":"Intertwined periodic sequences, Sturmian sequences and Beatty sequence","volume":"9","author":"TIJDEMAN R.","year":"1998","unstructured":"TIJDEMAN , R. 1998 b. Intertwined periodic sequences, Sturmian sequences and Beatty sequence . Indag. Math. (N.S.) 9 , 113 - 122 . TIJDEMAN, R. 1998b. Intertwined periodic sequences, Sturmian sequences and Beatty sequence. Indag. Math. (N.S.) 9, 113-122.","journal-title":"Indag. Math. (N.S.)"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00117-5"},{"key":"e_1_2_1_35_1","volume-title":"Generatingfunctionology","author":"WILF H.S.","unstructured":"WILF , H.S. 1994. Generatingfunctionology . 2 nd ed. Academic Press , Orlando, Fla . WILF, H.S. 1994. Generatingfunctionology. 2nd ed. Academic Press, Orlando, Fla.","edition":"2"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/347476.347482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T23:37:36Z","timestamp":1672616256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/347476.347482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,7]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2000,7]]}},"alternative-id":["10.1145\/347476.347482"],"URL":"http:\/\/dx.doi.org\/10.1145\/347476.347482","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,7]]},"assertion":[{"value":"2000-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}