Discrete Math Seminar (홍성필, 서울대, 16:00)

상일 2008.10.28 23:18 조회 수 : 11456


***** 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.

댓글 0

번호 제목 글쓴이 날짜 조회 수
284 학부 콜로퀴움(조철현 교수[서울대 수리과학부]),2008.12.4(목),오후5:30-6:30) 과사무실 2008.11.28 3496
283 Graduate Student Seminar in ASARC (11월 24일 (월) 오후 4:00) 과사무실 2008.11.24 941
282 Graduate Student Seminar in ASARC (12월 1일 (월) 오후 5:00) 과사무실 2008.11.24 896
281 응용수학 세미나(금,3:00,김용정교수) 과사무실 2008.11.18 1503
280 세미나안내(임선희박사 초청 강연 2008.12.10(수),16:00) 과사무실 2008.11.10 2852
279 Discrete Math Seminar (노유미, 인천대, 16:00) 상일 2008.11.10 11454
278 계산수학 세미나(양성대 박사[국가수리과학연구소]),2008.11.7(금),16:30) 과사무실 2008.11.05 1242
277 함수 해석학 세미나(이훈희박사,2008.11.6(목),16:00) 과사무실 2008.11.04 2011
276 ASARC 정기세미나(박희숙, ASARC, 16:30) 과사무실 2008.10.30 1320
» Discrete Math Seminar (홍성필, 서울대, 16:00) 상일 2008.10.28 11456
274 응용수학 세미나(목,4:30,송경우경희대교수) 과사무실 2008.10.28 1970
273 Discrete Math Seminar (정하웅, KAIST, 16:00) 상일 2008.10.17 1453
272 2008 가을 학부생 콜로퀴움(2008.10.16(목),17:30) 과사무실 2008.10.13 1110
271 ASARC 정기세미나(강순이, ASARC, 16:30) 과사무실 2008.10.09 1765
270 가을학기 콜로퀴움(김영훈 교수[서울대학교]),2008.12.5(금),16:00) 과사무실 2008.10.02 1470
269 가을학기 콜로퀴움(이준엽 교수 [이화여자대학교]),2008.11.27(목),16:00) 과사무실 2008.10.02 2829
268 가을학기 콜로퀴움(Prof. David Eisenbud [U.C. Berkeley]) 과사무실 2008.10.02 1324
267 가을학기 콜로퀴움(Prof. krzysztof Pawalowski[Adam Mickiewicz Univ.]) 과사무실 2008.10.02 1229
266 가을학기 콜로퀴움(오프리트 정 교수[KAIST 전산학과]),2008.10.31(금),16:00) 과사무실 2008.10.01 1583
265 가을학기 콜로퀴움(최윤서 교수[고등과학원]),2008.10.17(금),16:00) 과사무실 2008.10.01 1885