BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:ed324eab-014a-42bb-abe6-5c0caa979f47
X-WR-CALNAME:GT AlgoDist\, «A Parameterized-Complexity Framework for Findin
 g Local Optima»\, Nils Morawietz
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20271031T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20261025T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20250330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20260329T020000
RDATE:20270328T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ed324eab-014a-42bb-abe6-5c0caa979f47
DTSTAMP:20260411T142906Z
CLASS:PUBLIC
DESCRIPTION:Nils Morawietz (LaBRI)\n\nTitle: A Parameterized-Complexity Fra
 mework for Finding Local Optima\n\nAbstract:\n\nLocal search is a fundamen
 tal optimization technique that is both widely used in practice and deeply
  studied in theory\, yet its computational complexity remains poorly under
 stood. The traditional frameworks\, PLS and the standard algorithm problem
 \, introduced by Johnson\, Papadimitriou\, and Yannakakis (1988) fail to c
 apture the methodology of local search algorithms: PLS is concerned with f
 inding a local optimum and not with using local search\, while the standar
 d algorithm problem restricts each improvement step to follow a fixed pivo
 ting rule. In this work\, we introduce a novel formulation of local search
  which provides a middle ground between these models. In particular\, the 
 task is to output not only a local optimum but also a chain of local impro
 vements leading to it. With this framework\, we aim to capture the challen
 ge in designing a good pivoting rule. Especially\, when combined with the 
 parameterized complexity paradigm\, it enables both strong lower bounds an
 d meaningful tractability results. Unlike previous works that combined par
 ameterized complexity with local search\, our framework targets the whole 
 task of finding a local optimum and not only a single improvement step. Fo
 cusing on two representative meta-problems – Subset Weight Optimization Pr
 oblem with the c-swap neighborhood and Weighted Circuit with the flip neig
 hborhood – we establish fixed-parameter tractability results related to th
 e number of distinct weights\, while ruling out an analogous result when p
 arameterized by the distance to the nearest optimum via a new type of redu
 ction.\n\n\n\n\n\nhttps://algodist.labri.fr/index.php/Main/GT\n\nImport au
 tomatique depuis https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.
 fr/gt.algo-dist.ics par sync_icals_to_drupal.py pour gt-algodist
DTSTART;TZID=Europe/Paris:20260209T110000
DTEND;TZID=Europe/Paris:20260209T120000
LOCATION:LaBRI 178
SEQUENCE:0
SUMMARY:GT AlgoDist\, «A Parameterized-Complexity Framework for Finding Loc
 al Optima»\, Nils Morawietz
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
