Multiple optima in local search |
| |
| Institution: | 1. Departamento de Medicina Interna, Hospital Universitario HM Monteprincipe, HM Hospitales, Madrid, Spain;2. Facultad de Medicina, Universidad San Pablo-CEU, CEU Universities, Madrid, Spain;3. Fundación de Investigación, HM Hospitales, Madrid, Spain;4. Facultad de Ciencias Experimentales, Universidad Francisco de Vitoria, Madrid, Spain;5. Departamento de Seguridad, Salud y Bienestar de HM Hospitales, Madrid, Spain;6. Servicio de Laboratorio, HM Hospitales, Madrid, Spain;7. Departamento de Cardiología, Centro Integral de Enfermedades Cardiovasculares (CIEC), Hospital Universitario HM Monteprincipe, Madrid, Spain;8. Centro Nacional de Investigaciones Cardiovasculares (CNIC), Instituto de Salud Carlos III, Madrid, Spain;1. Department of Radiooncology and Radiotherapy, Charite University Hospital, Berlin;2. German Cancer Research Center (DKFZ), Heidelberg, and German Cancer Consortium (DKTK) Partner Site Berlin;3. Institute of Pathology, University Hospital and National Center for Tumor Diseases, Heidelberg, Germany;4. Department of Patholog, Center for Integrated Diagnostics, Massachusetts General Hospital/Harvard Medical School, Boston, USA;5. Department of Radiation Oncology, University Hospitals Erlangen-Nürnberg, Erlangen;6. Department of Radiotherapy, University Hospital Regensburg;7. Department of Otorhinolaryngology, Head & Neck Surgery, University Hospital Giessen-Marburg, Marburg;8. Institute of Pathology, Technical University Munich (TUM), Munich;9. German Cancer Research Center (DKFZ), Heidelberg, and German Cancer Consortium (DKTK) partner site Munich, Germany;1. Division of Medical Oncology, University of Colorado School of Medicine, Aurora;2. Medical University of South Carolina, Charleston;3. Karmanos Cancer Institute, Detroit, USA;4. Department of Medical Oncology, British Columbia Cancer Agency, Vancouver, Canada;5. Oncology and Hematology Associates of South West Virginia, Roanoke;6. Department of Medical Oncology, Virginia Cancer Specialists, Fairfax;7. US Oncology Research, The Woodlands;8. Texas Oncology, Round Rock, USA;9. London Health Sciences Centre, London, Canada;10. Oncothyreon, Inc., Seattle;11. Abramson Cancer Center of the University of Pennsylvania, Philadelphia, USA |
| |
| Abstract: | We consider the application of local search methods to the maximum independent set problem. These methods employ a relation R on the power set of the graph's vertices that identifies a set of vertices, U, with a collection of subsets of vertices, R(U), called the neighbors of U. If each set U has only polynomially many neighbors then we say that R is polynomially bounded. Further, given a graph, G, we call a permutation of G, φ(G), to be any graph that arises from G by relabeling the vertices. Our main result is slightly stronger than the following: we construct a graph G such that, for all polynomially bounded relations, R, most permutations φ(G) of the graph contain exponentially many strict local optima that are not global optima. That is, a single graph (up to relabelling of the vertices) exists that soundly defeats all polynomially bounded relations R. Corollaries follow for 0–1 integer programming and other hard optimization problems. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
