{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T18:22:35Z","timestamp":1648837355472},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:p> We investigate the problem of devising an optimal time strategy to send messages from one site to another in a Store and Forward network. We consider the problem both in the cases of messages transmitted through fixed paths and through dynamically variable paths, respectively. In particular, we prove that both of versions are NP-complete even when very restrictive hypotheses are imposed on the network topology and on the required amount of time. We thus turn our attention towards the study of the approximability of this scheduling problem. In particular, we prove the following negative results: <\/jats:p><jats:p> (i) In the case of fixed paths, the problem is not approximable for any constant approximation ratio unless P is equal to NP. <\/jats:p><jats:p> (ii) In the case of arbitrary paths, the problem is not approximable for any constant approximation ratio (unless P is equal to NP) when an arbitrary priority function is defined on the set of messages. <\/jats:p><jats:p> Finally, we present a particular network topology in which the problem can be solved in deterministic polynomial time. <\/jats:p>","DOI":"10.1142\/s0129054195000111","type":"journal-article","created":{"date-parts":[[2004,11,12]],"date-time":"2004-11-12T11:59:25Z","timestamp":1100260765000},"page":"155-168","source":"Crossref","is-referenced-by-count":0,"title":["OPTIMUM SCHEDULE PROBLEMS IN STORE AND FORWARD NETWORKS"],"prefix":"10.1142","volume":"06","author":[{"given":"ANDREA","family":"CLEMENTI","sequence":"first","affiliation":[{"name":"Dipartimento di Scienze dell\u2019Informazione,  Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria, 113\u201300198 Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MIRIAM DI","family":"IANNI","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze dell\u2019Informazione,  Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria, 113\u201300198 Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054195000111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:44:30Z","timestamp":1565138670000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054195000111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1995,6]]}},"alternative-id":["10.1142\/S0129054195000111"],"URL":"https:\/\/doi.org\/10.1142\/s0129054195000111","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}