Analysis of greedy expert hiring and an application to memory-based learning (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Analysis of greedy expert hiring and an application to memory-based learning (extended abstract)

Full text

Pdf (698 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the ninth annual conference on Computational learning theory table of contents

Desenzano del Garda, Italy

Pages: 217 - 223

Year of Publication: 1996

ISBN:0-89791-811-8

Author

Igal Galperin

Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 27, Citation Count: 0

Additional Information:

references 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/238061.238101 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	A. Blum, Learning boolean functions in an infinite attribute space, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.64-72, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100224]
	2	Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Proceedings of the fourth annual workshop on Computational learning theory, p.157-166, August 05-07, 1991, Santa Cruz, California, United States
	3	V. Chv~tal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, 1979.
	4	G. Comuejols, M.L. Fisher, and G.L. Nemhauser. Location of bank accounts to optimize float: An analytical study of exact and approximate algorithms. Management Science, 23:789-810, 1977.
	5	George B. Dantzig. Activity Analysis of Production and Allocation, chapter Programming of Interdependent Activities, II, Mathematical Models, pages 19-32. John Wiley and Sons Inc., New York, 1951.
	6	M.L. Fisher and D.S. Hochbaum. Probabilistic analysis of the planar k-median problem. Mathematics of Operations Research, 5(1):265-294, Feb 1980.
	7	David Haussler , Phil Long, A GENERALIZATION OF SAUER''S LEMMA, University of California at Santa Cruz, Santa Cruz, CA, 1990
	8	David Haussler, DECISION THEORETIC GENERALIZATIONS OF THE PAC MODEL FORNEURAL NET AND OTHER LEARNING APPLICATIONS, University of California at Santa Cruz, Santa Cruz, CA, 1990
	9	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	10	D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256-278, 1974.
	11	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	12	L.G.Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20:191-194, 1979.
	13	Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
	14	Jyh-Han Lin , Jeffrey Scott Vitter, A theory for memory-based learning, Proceedings of the fifth annual workshop on Computational learning theory, p.103-115, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130397]
	15	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	16	L.H. Loomis and S. Stemberg. Advanced Calculus. Addison-Wesley, 1968.
	17	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	18	D. Marr. A theory for cerebral neocortex. In Proceedings of the Royal Society of London B., 176, pages 161-234, 1970.
	19	N. Megiddo and K.J. Supowit. On the complexity of some common geometric location problems. Siam Journal on Computing, 13:182-196, 1984.
	20	G.L. Nemhauser and L.A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3): 177-188, 1978.
	21	G.L. NemhauserandL.A. Wolsey. Maximizingsubmodular set functions: Formulations and analysis of algorithms. In P. Hansen, editor, Studies on Graphs and Discrete Programming, volume 11 of Annals of Discrete Mathematics, pages 279-301. North-Holland, 1981.
	22	G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming, 14:265-294, 1978.
	23	Guillermo Owen. Game Theory. Academic Press, 1982.
	24	C.H. Papadimitriou. Worst-case and probabilistic analysis of a geometric location problem. Siam Journal on Computing, 10:542-557, 1981.
	25	Lloyd S. Shapley. Cores of convex games. International Journal of Game Theory, 1(1): 11-26, 1971.