BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190716T163000
DTEND;TZID=Asia/Seoul:20190716T173000
DTSTAMP:20260423T072540
CREATED:20190627T074550Z
LAST-MODIFIED:20240707T090234Z
UID:1060-1563294600-1563298200@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Integrality of set covering polyhedra and clutter minors
DESCRIPTION:Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$\, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem\, also known as the hitting set problem\, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron\, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general\, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral\, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming. \nIn this talk\, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality\, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal\, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters\, namely\, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor. \nThis talk is based on joint works with Ahmad Abdi and Gérard Cornuéjols.
URL:https://dimag.ibs.re.kr/event/2019-07-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR