The data broadcast problem with non-uniform transmission times

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

The data broadcast problem with non-uniform transmission times

Full text

Pdf (1.08 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 547 - 556

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

Claire Kenyon	LRI, Université Paris XI, Bâtiment 490, F-91405, Orsay, France
Nicolas Schabanel	LIP, ENS Lyon, 46, allée d'Italie, F-69364 Lyon Cedex 07, France

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 26, Citation Count: 14

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

Warning: The download time has expired please click on the item to try again.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Swarup Acharya , Stanley Zdonik, Broadcast disks: dissemination-based data management for asymmetric communication environments, 1998
	2	AMMAR, M. H. Response time in a teletext system: An individual user's perspective. IEEE Transactions on Communications COM-35,11 (Nov. 1987), 1159--1170.
	3	#AR, M. H., AND WONG, J. W. The design of teletext broadcast cycles. In Performance Evaluation (1985), vo}. 5(4), pp. 2.3,5-242.
	4	AM#tAR, M. H., AND WONG, J. W. On the optimality of cyclic transmission in teletext systems. In IEEE Trans. on Comm. (1987), vol. COM-35(11), pp. 1159-1170.
	5	Shoshana Anily , Celia A. Glass , Refael Hassin, The scheduling of maintenance service, Discrete Applied Mathematics, v.82 n.1-3, p.27-42, March 2, 1998 [doi>10.1016/S0166-218X(97)00119-4]
	6	Amotz Bar-Noy , Randeep Bhatia , Joseph Naor , Baruch Schieber, Minimizing service and operation costs of periodic scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 25-27, 1998, San Francisco, California, United States
	7	Mee Yee Chan , Francis Y. L. Chin, General Schedulers for the Pinwheel Problem Based on Double-Integer Reduction, IEEE Transactions on Computers, v.41 n.6, p.755-768, June 1992 [doi>10.1109/12.144627]
	8	CleAN, M. Y., AND CHris, F. Schedulers for larger classes of pinwheel instances. Algorithmica 9 (Jun. 1993), 425--462.
	9	Jan Gecsei, The Architecture of Videotex Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1983
	10	HADLEY, G., AND WHITIN, T. M. Analysis of inventory systems. Prentice-Hall, 1963.
	11	Micha Hofri , Zvi Rosberg, Packet delay under the golden ratio weighted tdm policy in a multiple-access channel, IEEE Transactions on Information Theory, v.33 n.3, p.341-349, May 1, 1987 [doi>10.1109/TIT.1987.1057317]
	12	HOLTE, R., MOK, A., RosmR, L., TULCtIINSKY, I., AND VARVEL, D. The pinwheel: A real-time scheduling problem. In Proc. 2#nd Hawaii Int. Conf. Syst. Sci. (Jan. 1989), pp. 693-702.
	13	ITAI, A., AND ROSBERG, S. A golden ratio control policy for a multiple-access channel. IEEE Transactions on Autom. Contr. A C-#9 (Aug. 1984).
	14	Sanjeev Khanna , Vincenzo Liberatore, On broadcast disk paging, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.634-643, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276879]
	15	Sanjeev Khanna , Shiyu Zhou, On indexed data broadcast, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.463-472, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276859]
	16	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	17	Chi-Jiun Su , Leandros Tassiulas, Broadcast Scheduling for Information Distribution, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.109, April 09-11, 1997
	18	Sohail Hameed , Nitin Vaidya, Efficient Algorithms for Scheduling Single and Multiple Channel Data Broadcast, Texas A & M University, College Station, TX, 1997
	19	Sohail Hameed , Nitin H. Vaidya, Log-time algorithms for scheduling single and multiple channel data broadcast, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.90-99, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262136]
	20	YOUNG, N. E., Ta_#hl#, R. E., A#D Ore,m, J. B. Faster parametric shortest path and minimum balances algorithms. In Nettoorks (Mar. 1991), #oI. 21(2).

CITED BY 14

	Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly-periodic schedules, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.107-116, August 2001, Newport, Rhode Island, United States
	Thomas Erlebach , Alexander Hall, NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.194-202, January 06-08, 2002, San Francisco, California
	Claire Kenyon , Nicolas Schabanel , Neal Young, Polynomial-time approximation scheme for data broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.659-666, May 21-23, 2000, Portland, Oregon, United States
	Amotz Bar-Noy , Joseph Naor , Baruch Schieber, Pushing dependent data in clients-providers-servers systems, Proceedings of the 6th annual international conference on Mobile computing and networking, p.222-230, August 06-11, 2000, Boston, Massachusetts, United States
	Amotz Bar-Noy , Joseph Naor , Baruch Schieber, Pushing dependent data in clients-providers-servers systems, Wireless Networks, v.9 n.5, p.421-430, September 2003
	Vincenzo Liberatore, Caching and Scheduling for Broadcast Disk Systems, Journal of Experimental Algorithmics (JEA), 6, p.5-es, 2001
	Amotz Bar-Noy , Boaz Patt-Shamir , Igor Ziper, Broadcast disks with polynomial cost functions, Wireless Networks, v.10 n.2, p.157-168, March 2004
	Thomas Erlebach , Alexander Hall, NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow, Journal of Scheduling, v.7 n.3, p.223-241, May-June 2004
	Amotz Bar-Noy , Aviv Nisgav , Boaz Patt-Shamir, Nearly optimal perfectly periodic schedules, Distributed Computing, v.15 n.4, p.207-220, December 2002
	Francisco Javier Ovalle-Martínez , Julio Solano González , Ivan Stojmenović, A parallel hill climbing algorithm for pushing dependent data in clients-providers-servers systems, Mobile Networks and Applications, v.9 n.4, p.257-264, August 2004
	Joel L. Wolf , Mark S. Squillante , John J. Turek , Philip S. Yu , Jay Sethuraman, Scheduling Algorithms for the Broadcast Delivery of Digital Products, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.721-741, September 2001
	Elia Ardizzoni , Alan A. Bertossi , M. Cristina Pinotti , Shashank Ramaprasad , Romeo Rizzi , Madhusudana V. S. Shashanka, Optimal Skewed Data Allocation on Multiple Channels with Flat Broadcast per Channel, IEEE Transactions on Computers, v.54 n.5, p.558-572, May 2005
	S. Anticaglia , F. Barsi , A. A. Bertossi , L. Iamele , M. C. Pinotti, Efficient heuristics for data broadcasting on multiple channels, Wireless Networks, v.14 n.2, p.219-231, March 2008
	Jonathan Beaver , Kirk Pruhs , Panos K. Chrysanthis , Vincenzo Liberatore, Improving the Hybrid Data Dissemination Model of Web Documents, World Wide Web, v.11 n.3, p.313-337, September 2008