Dabeen Lee (이다빈), Integrality of set covering polyhedra and clutter minors

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

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

Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)

Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔) 

Special Session @ 2019 KSIAM Annual MeetingA special session on "Combinatorial and Discrete Optimization" at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcomeDateNov 8, 2019 – Nov 9, 2019 Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)VenueVenezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔)  Address: 61-13 Odongdo-ro, Sujeong-dong,

Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure

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

Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called "cutting-plane" algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but

Dabeen Lee (이다빈), Mixing sets, submodularity, and chance-constrained optimization

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

A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we

Dabeen Lee (이다빈), Non-smooth and Hölder-smooth submodular optimization

Room 1501, Bldg. E6-1, KAIST

We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an guarantee when the function is monotone and Hölder-smooth, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that

Dabeen Lee (이다빈), From coordinate subspaces over finite fields to ideal multipartite uniform clutters

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

Take a prime power $q$, an integer $n\geq 2$, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper, we

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.