Loading Events

« All Events

  • This event has passed.
:

Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row

July 14 Wednesday @ 5:00 PM - 6:00 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Stefan Weltge
Technical University of Munich
https://www.weltge.de

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1.

We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky.

Details

Date:
July 14 Wednesday
Time:
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:

Venue

Room B232
IBS (기초과학연구원)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.