Improved bounds for acyclic job shop scheduling (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved bounds for acyclic job shop scheduling (extended abstract)

Full text

Pdf (1.42 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 624 - 633

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Uriel Feige	Dept. of Appl. Math. and Comp. Sci. Weizmann Institute, 76100 Rehovot, Israel
Christian Scheideler	Dept. of Math. and Comp. Sci., Paderborn University, 33095 Paderborn, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 15, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276878 What is a DOI?

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	N. Alon, J. Spencer, P. Erdgs. The ProMbilistic Method. Wiley intersdence Series in Discrete Mathematics and Optimization, John Wiley &: Sons, 1992.
	2	J. Beck. An algorithmic approach to the LovS. sz local lemma. Random Structures and Algorithms 2(4), pp. 343-365, 1991.
	3	Leslie Ann Goldberg , Mike Paterson , Aravind Srinivasan , Elizabeth Sweedyk, Better approximation guarantees for job-shop scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.599-608, January 05-07, 1997, New Orleans, Louisiana, United States
	4	M. Hofri, Probabilistic analysis of algorithms: on computing methodologies for computer algorithms performance evaluation, Springer-Verlag New York, Inc., New York, NY, 1987
	5	T. Leighton, B. Maggs, S. Rao. Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Combinatorica 14, pp. 167-186, 1994.
	6	T. Leighton, B. Maggs, A. Richa. Fast algorithms for finding O(congestion+dilation) packet routing schedules. Technical Report CMU-C8--96-152, School of Computer Sdence, Carnegie Mellon University, Pittsburgh, PA, USA, 1996.
	7	Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258659]
	8	Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
	9	David B. Shmoys , Clifford Stein , Joel Wein, Improved Approximation Algorithms for Shop Scheduling Problems, SIAM Journal on Computing, v.23 n.3, p.617-632, June 1994 [doi>10.1137/S009753979222676X]
	10	D. Williamson, L. Hall, J. Hoogeveen, C. Hurkens, J. Lenstra, S. Sevastjanov, D. Shmoys. "Short shop schedules". Operations Research, 1996.

CITED BY 8

	Artur Czumaj , Christian Scheideler, A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.38-47, May 21-23, 2000, Portland, Oregon, United States
	Artur Czumaj , Christian Scheideler, Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.30-39, January 09-11, 2000, San Francisco, California, United States
	Matthew Andrews , Lisa Zhang, Packet routing with arbitrary end-to-end delay requirements, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.557-565, May 01-04, 1999, Atlanta, Georgia, United States
	Maurice Queyranne , Maxim Svirdenko, New and improved algorithms for minsum shop scheduling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.871-878, January 09-11, 2000, San Francisco, California, United States
	Uriel Feige , Giora Rayzman, On the drift of short schedules, Theoretical Computer Science, v.289 n.1, p.473-484, 23 October 2002
	Eric Anderson , Dirk Beyer , Kamalika Chaudhuri , Terence Kelly , Norman Salazar , Cipriano Santos , Ram Swaminathan , Robert Tarjan , Janet Wiener , Yunhong Zhou, Value-maximizing deadline scheduling and its application to animation rendering, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	F. Pezzella , G. Morganti , G. Ciaschetti, A genetic algorithm for the Flexible Job-shop Scheduling Problem, Computers and Operations Research, v.35 n.10, p.3202-3212, October, 2008
	Viswanath Nagarajan , Maxim Sviridenko, Tight Bounds for Permutation Flow Shop Scheduling, Mathematics of Operations Research, v.34 n.2, p.417-427, May 2009