6 papers
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…
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…
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…
Flipping odd matchings in geometric and combinatorial settings
Oswin Aichholzer, Sofia Brenner, Joseph Dorfer +4
We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched ve…
Signotopes with few plus signs
Helena Bergold, Lukas Egeling, Hung. P. Hoang
Arrangements of pseudohyperplanes are widely studied in computational geometry. A rich subclass of pseudohyerplane arrangements, which has gained more attention in recent years, is…
Generating all invertible matrices by row operations
Petr Gregor, Hung P. Hoang, Arturo Merino +1
We show that all invertible matrices over any finite field can be generated in a Gray code fashion. More specifically, there exists a listing such that…