• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Don't Be Strict in Local Search!

Gaspers, Serge; Kim, Eun Jung; Ordyniak, Sebastian; Saurabh, Saket; Szeider, Stefan (2012), Don't Be Strict in Local Search!, in Selman, Bart; Hoffmann, Jörg, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press

Type
Communication / Conférence
External document link
http://arxiv.org/abs/1208.1688v3
Date
2012
Conference title
AAAI 2012
Conference date
2012-07
Conference city
Toronto
Conference country
Canada
Book title
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Book author
Selman, Bart; Hoffmann, Jörg
Publisher
AAAI Press
ISBN
978-1-57735-568-7
Metadata
Show full item record
Author(s)
Gaspers, Serge

Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ordyniak, Sebastian

Saurabh, Saket

Szeider, Stefan
Abstract (EN)
Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a na\"ive brute-force search of the k-exchange neighborhood requires n to the power of O(k) time, which is not practical even for very small values of k. Fellows et al. (IJCAI 2009) studied whether this brute-force search is avoidable and gave positive and negative answers for several combinatorial problems. They used the notion of local search in a strict sense. That is, an improved solution needs to be found in the k-exchange neighborhood even if a global optimum can be found efficiently. In this paper we consider a natural relaxation of local search, called permissive local search (Marx and Schlotter, IWPEC 2009) and investigate whether it enhances the domain of tractable inputs. We exemplify this approach on a fundamental combinatorial problem, Vertex Cover. More precisely, we show that for a class of inputs, finding an optimum is hard, strict local search is hard, but permissive local search is tractable. We carry out this investigation in the framework of parameterized complexity.
Subjects / Keywords
combinatorial optimization; Local Search

Related items

Showing items related by title and author.

  • Thumbnail
    The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation 
    Kim, Eun Jung; Ordyniak, Sebastian; Szeider, Stefan (2014) Communication / Conférence
  • Thumbnail
    Valued-Based Argumentation for Tree-like Value Graphs 
    Kim, Eun Jung; Ordyniak, Sebastian (2012) Chapitre d'ouvrage
  • Thumbnail
    Solving hard cut problems via flow-augmentation 
    Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2021) Communication / Conférence
  • Thumbnail
    Electronic energy and electron transfer processes in photoexcited donor-acceptor dyad and triad molecular systems based on triphenylene and perylene diimide units 
    Lee, K. J.; Woo, J. H.; Kim, Eun Jung; Xiao, Y.; Su, X.; Mazur, L. M. (2015) Article accepté pour publication ou publié
  • Thumbnail
    A survey of open questions in adaptive therapy : bridging mathematics and clinical translation 
    West, Jeffrey; Adler, Fred; Gallaher, Jill; Strobl, Maximilian; Brady-Nicholls, Renee; Brown, Joel S.; Robertson-Tessi, Mark; Kim, Eun Jung; Noble, Robert; Viossat, Yannick; Basanta, David; Anderson, Alexander R. A. (2022) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo