C. H. Papadimitriou
- {Be} J. L. Bentley, "Experiments on Traveling Salesman Heuristics," Proc. First SIAM Symposium on Discrete Algorithms, pp. 91-99, 1990. Google Scholar
Digital Library
- {GJ} M. R. Garey and D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-completeness , Freeman, 1979. Google ScholarDigital Library
- {Go} G. Godbeer "On the Computational Complexity of the Stable Configuration Problem for Connectionist Models," Master's Thesis, U. Toronto CS, 1987.Google Scholar
- {HL} A. Haken, M. Luby "Steepest Descent Can Take Exponential Time for Symmetric Connection Networks," Complex Systems 2(1988), pp. 191- 196. Google ScholarDigital Library
- {Ho} J. J. Hopfield "Neural Networks and Physical Systems with Emergent Collective Computational Capabilities," Proc. Nat. Acad. Sci. 79(1982), pp. 2554-2558.Google ScholarCross Ref
- {HT} J. J. Hopfield and D. W. Tank, Neural Computation of Decisions in Optimization Problems, Biol. Cyber. 52(1985), pp. 141-152.Google ScholarDigital Library
- {Jo} D. S. Johnson, private communication, 1988.Google Scholar
- {JPY} D. S. Johnson, C. H. Papadimitriou, M. Yannakakis "How Easy is Local Search?" Proc. 26th Annual Symp. Foundations Comp. Sci., 1985, pp. 39-42; also, J. Comp. Syst. Sci., 37(1988), pp. 79-100. Google ScholarDigital Library
- {KW} R. M. Karp, A. Wigderson "A Fast Parallel Algorithm for the Maximal Independent Set Problem," Proc. 16th Annual Symp. on Theory of Computing, 1984, pp. 266-272; also, J. ACM 32(1985) pp. 762-773. Google ScholarDigital Library
- {Ke} W. Kern, A Probabilistic Analysis of the Switching Algorithm for the Euclidean TSP, Math. Programming 44 (1989), pp. 213-219. Google ScholarDigital Library
- {KL} B. W. Kernighan, S. Lin "An Efficient Heuristic Procedure for Partitioning Graphs," Bell S. T. J. 49(1970) pp. 291-307.Google ScholarCross Ref
- {Kr} M. W. Krentel "On Finding Locally Optimal Solutions," Proc. 4th Annual Structure in Complexity Conf., 1989, pp. 132-137; also, SIAM J. Comp., in press.Google Scholar
- {Kr1} M. W. Krentel, "Structure of Locally Optimal Solutions," Proc. 30th Annual Symp. Foundations Comp. Sci., 1989, pp. 216-221.Google ScholarDigital Library
- {LK} S. Lin, B. W. Kernighan "An Effective Heuristic for the Traveling Salesman Problem," O. R. 21(1973) pp. 498-516.Google ScholarDigital Library
- {Li} J. Lipscomb "On the Computational Complexity of Finding a Connectionist Model's Stable State of Vectors," Master's Thesis, Dept. of CS, Univ. of Toronto, 1987.Google Scholar
- {Lub} M. Luby "A Simple Parallel Algorithm for the Maximal Independent Set Problem (Extended Abstract)," in Proc. 17th Annual Symp. Theory of Computing, 1985, pp. 1-10; full paper in SIAM J. Comp. 15(1986), pp. 1036-1053. Google ScholarDigital Library
- {Lue} G. Lueker, Unpublished notes on two-changes, manuscript, Princeton University, 1975.Google Scholar
- {MP} N. Megiddo, C. H. Papadimitriou "A Note on Total Functions, Existence Theorems, and Computational Complexity," IBM Research Report RJ 7091, 1989.Google Scholar
- {Pap} C. H. Papadimitriou, "Bideterministic Computation," manuscript, 1990.Google Scholar
- {Pap1} C. H. Papadimitriou, "The Complexity of the Lin-Kernighan Algorithm," submitted to Math. O.R.Google Scholar
- {PS} C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity , Prentice-Hall, 1982. Google ScholarDigital Library
- {Par} I. Parberry "A Primer on the Complexity Theory of Neural Networks," to appear in A Source-book on Formal Techniques in Artificial Intelligence , R. B. Banerji, ed., Elsevier, 1989.Google Scholar
- {SY} A. A. Schäffer and M. Yannakakis "Simple Local Search Problems That Are Hard to Solve," SIAM J. Comp., to appear. Google ScholarDigital Library
- {To} C. A. Tovey, "Low Order Polynomial Bounds on the Expected Performance of Local Improvement Algorithms," Mathematical Programming 35(1986), pp. 193-224. Google ScholarDigital Library
- {Ya} M. Yannakakis, "The Analysis of Local Search Problems and Their Heuristics," Proc. 1990 Symp. Theoretical Aspects of Comp. Sci.. Google ScholarDigital Library
Index Terms
- On the complexity of local search
Recommendations
The Effect of Local Website Search
KSE '09: Proceedings of the 2009 International Conference on Knowledge and Systems EngineeringGlobal search engine is a huge but it can’t replace local search engine. The local search engines help the end-user to retrieve easily what they want and to give accurate results than global search engines do. The end-user can also use the global search ...
Personalization of Content Ranking in the Context of Local Search
WI-IAT '09: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 01Ranking search results using a single ranking function for all search engine visitors is inherently bounded in the performance the ranking algorithm can achieve when considering the variety of requirements of Web searchers and the proliferation of ...
A Crawler for Local Search
ICDS '10: Proceedings of the 2010 Fourth International Conference on Digital SocietyVertical search engines enable users to find information related to a certain topic. A local search engine is a vertical search engine whose topic revolves around a certain geographical area (such as a city, state, country, etc…) In this paper we ...
Comments