BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:When to Identify Is to Control: On the Controllability of Combinat
 orial Optimization Problems [Oberseminar Discrete Optimization]
DTSTART:20260706T161500Z
DTEND:20260706T171500Z
DTSTAMP:20260719T034000Z
UID:indico-event-1273@math-events.uni-bonn.de
DESCRIPTION:Speakers: Jannik Matuschke (KU Leuven)\n\nConsider a finite gr
 ound set E\, a set of solutions X in R^E and a class of objective function
 s C on X. We are interested in subsets S of E that can control X in the se
 nse that we can induce any given solution x in X as an optimum for any giv
 en objective function c in C by adding linear terms to c on the coordinate
 s corresponding to S. We observe that if X is either a convex set or consi
 sts of binary vectors\, then a set S controls X if and only if it enables 
 us to identify any given solution by its coordinates on S. For the case th
 at X is convex\, we moreover show that the sets controlling X induce a mat
 roid. As a consequence\, min-weight controlling sets can be computed effic
 iently from a representation of the affine hull of X in this case.\nWhile 
 the aforementioned result extends to the case where X is the set of bases 
 of a matroid\, other natural discrete structures are much less tractable: 
 In particular\, when X is the set of s-t-paths in a directed graph\, decid
 ing whether an identifying set of a certain cardinality exists is Sigma-2-
 P-complete. The problem remains NP-hard even when the underlying graph is 
 acyclic\, but we derive an approximation for this case by establishing a t
 ight bound on the gap between the size identifying sets for X and the size
  of identifying sets for its convex hull.\nThis is joint work with Max Kli
 mm.\n \nThe Oberseminar takes place in the Seminarraum\, 1st floor. Parti
 cipants are invited to have coffee or tea in the lounge before.\n \n\nhtt
 ps://math-events.uni-bonn.de/event/1273/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/1273/
END:VEVENT
END:VCALENDAR