Combinatorial Reconfiguration (17w5066)


(University of Waterloo)

(Tohoku University)

Amer Mouawad (University of Bergen)


The Banff International Research Station will host the "Combinatorial Reconfiguration" workshop in Banff from January 22 to January 27, 2017.

Reconfiguration is the study of the transformation of solutions to a problem. The difficulty of solving the original problem may or may not indicate the difficulty of transforming one solution into another in such a way that the result of each step of the transformation is also a solution. As a concrete example of a problem, we consider the assignment of customers to power stations such that each customer obtains as much power as is required without exceeding the capacity of what each station can produce. Each such assignment can be viewed as a solution. When a station needs to be repaired, it may be necessary to change to another assignment, moving customers one-by-one to minimize disruptions.

The goal of the workshop is to bring together researchers in this new field, helping us to develop general approaches to reconfiguration problems as well as to understand what properties of problems make reconfiguration more or less difficult to accomplish. For certain problems, the key factor might be the way that a transformation step is defined. For others, it may depend on what types of solutions are considered to be valid, or restrictions on the possible inputs. Meeting with researchers in related areas will help to broaden the impact of the work, and take advantage of the synergy of ideas and approaches.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).