דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event date icon
יום ראשון, 07.02.2021, 17:00
event location icon
We consider the REQUIREMENT CUT problem, where given an undirected graph G = (V, E) equipped with non-negative edge weights c , and g groups of vertices X1, . , Xg in V each equipped with a requirement ri, the goal is to find a collection of edges F in E, with total minimum weight, such that once F is removed from G in the resulting graph every Xi is broken into at least ri connected components. REQUIREMENT CUT captures multiple classic cut problems in graphs, e.g., MULTICUT, MULTIWAY CUT, MIN k-CUT, STEINER k-CUT, STEINER MULTICUT, and MULTI-MULTIWAY CUT. We present an approximation for the problem, our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.