***** KAIST Discete Math Semianr *****
DATE: November 14th, Friday
TIME: 4PM-5PM
PLACE: E6-1, ROOM 1409
SPEAKER: Sung-Pil Hong (홍성필), Seoul National University, Seoul, Korea.
TITLE: Approximability of a batch consolidation problem
We consider a problem of minimizing the number of batches of a fixed capacity processing the orders of various sizes on a finite set of items. This batch consolidation problem is motivated by the batch production system typical in raw material industries in which multiple items can be processed in the same batch in case they share sufficiently close production parameters. We focuse on the special case in which up to 2 items can be processed in a single batch. The problem is NP-hard and can not be approximated within 1.00142 of the optimum under the premise, P ≠ NP as can be shown by a polynomial reduction from the vertex cover problem with bounded degree. However, the problem admits a 3/2 -approximation. The idea is to decompose the orders of items so that a maximum matching in the graph on the vertices of the decomposed orders provides a well-consolidated batch set.
----------------------------------------------
Informations on future talks can be found at :
http://mathsci.kaist.ac.kr/~sangil/seminar/
Please email to sangil (at) kaist.edu if you wish to receive this
announcements in the future by email.