Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
We prove the all-exp property for the Traveling Salesman Problem with the -opt neighborhood, and for - and -Maximum Constraint Assignment with the flip neighbo…
cs.DS2026
Exponential Local Search in Bounded-Occurrence MAX-CSP
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
We study the number of improving steps that local search may require for -MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constrai…
cs.DS2026
Not All Degree Constraints Are Created Equal when Computing Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share…