&egr;-optimization schemes and L-bit precision (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

&egr;-optimization schemes and L-bit precision (extended abstract): alternative perspectives in combinatorial optimization

Full text

Pdf (890 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 565 - 572

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

James B. Orlin	M.I.T., Sloan School of Management, Operations Research Center, E40-149, Cambridge, MA
Andreas S. Schulz	M.I.T., Sloan School of Management, Operations Research Center, E53-361, Cambridge, MA
Sudipta Sengupta	M.I.T., Laboratory for Computer Science, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/335305.335377 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	Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
	2	R. Ahuja and J. Orlin. Inverse optimization,. Working paper, Sloan School of Management, M.I.T., August 1999.
	3	Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	4	Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
	5	D. Bertsekas. A distributed algorithm for the assignmerit problem. Working paper, Laboratory for Information and Decision Systems, M.I.T., 1979.
	6	W. Cody, J. Coonen, D. Gay, K. Hanson, D. Hough, W. Kahan, R. Karpinski, J. Palmer, F. Ris, and D. Stevenson. A proposed radix- and word-lengthindependent standard for floating point arithmetic. IEEE Micro, 4:86-100, 1984.
	7	G. Dantzig. Discrete-variable extremum problems. Operations Research, 5:266-277, 1957.
	8	W. F. de la Vega and G. Lueker. Bin packing can be solved within 1+~ in linear time. Combinatorica, 1:349- 355, 1981.
	9	Daniel W. Engels , David R. Karger , Stavros G. Kolliopoulos , Sudipta Sengupta , R. N. Uma , Joel Wein, Techniques for Scheduling with Rejection, Proceedings of the 6th Annual European Symposium on Algorithms, p.490-501, August 24-26, 1998
	10	M. Garey and D. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM journal on Computing, 4:397-411, 1975.
	11	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	12	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990 [doi>10.1287/moor.15.3.430]
	13	David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys (CSUR), v.23 n.1, p.5-48, March 1991 [doi>10.1145/103162.103163]
	14	R. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17:263- 269, 1969.
	15	Harvey J. Greenberg, An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, Advances in computational and stochastic optimization, logic programming, and heuristic search: interfaces in computer science and operations research, Kluwer Academic Publishers, Norwell, MA, 1997
	16	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	17	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
	18	Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
	19	IEEE. iEEE standard for binary floating-point arithmetic. SIGPLAN Notices, 22:9-25., 1985.
	20	J. Jackson. Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles, 1955.
	21	H. L. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538-547, 1983.
	22	N. Karmarkar and R. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science, pages 312-320, Chicago, Illinois, 1982. IEEE.
	23	R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.
	24	T.-C. Lai and J. Orlin. The complexity of preprocessing. Working paper, Sloan School of Management, M.I.T., 1998.
	25	S. Sengupta. Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. Manuscript, Laboratory for Computer Science, M.i.T., 1999.