Description
Abstract:
When a linear problem is infeasible, in most cases of real-life
applications it is not enough to say that there is no solution; we have to
obtain some "useful" result. The Minimum Feasibility Blocker (MinFB)
problem is as follows: it takes as input a system of linear inequalities
Ax ≤ b, and asks for a smallest subset whose removal leaves a feasible
problem. As this subset "blocks" the feasibility, we refer to it as a
feasibility blocker. Since the MinFB problem is NP-hard, we are going to
give an approach from the parameterized complexity theory. In this area,
the problem input of size n is additionally equipped with one or more
integer parameters k, and one measures the problem complexity in terms of
both n and k. The goal is to solve such an instance I by fixed-parameter
tractable algorithms (FPT), which run in time f(k)·poly(|I|) for some
computable function f.
The talk will be in English. After the talk, there will be a short virtual meeting with free discussion on any topic.
Please contact Tamás Király (tkiraly[at]cs.elte.hu) for Zoom access if you are not on the mailing list.