Seminars in November 2008

  • Yoomi Rho (노유미), Turán type problems forbidding complete graphs and complete multipartite graphs together
    Turán type problems forbidding complete graphs and complete multipartite graphs together
    Yoomi Rho (노유미)
    Dept. of Mathematics, Univ. of Incheon, Incheon, Korea.
    2008/11/28 Fri, 4PM-5PM
    A Turán type problem looks for the maximum number of edges of a graph of a given order that does not contain given forms of graphs as subgraphs. These given forms of subgraphs are called the forbidden graphs of the problem. This problem also looks for the forms of graphs which have the maximum number of edges. This line of research is started by Turán who solved the problem forbidding complete graphs in 1941. Problems forbidding complete bipartite graphs or even cycles have been considered. Also there are asymptotic results on problems forbidding complete multipartite graphs. In 1994, Brualdi and Mellendorf raised the following problem which forbids a complete graph and a complete bipartite graph together. </p>

    Let t and n be positive integers with n≥t≥2. Determine the maximum number of edges of a graph of order n that contains neither Kt nor Kt,t as a subgraph.

    They also solved this problem when n=2t. Obviously when n<2t, the problem reduces to Turán's problem which forbids only Kt. We solve the problem when n=2t+1. We raise a problem which forbids Kt and Kt,n-t together and a problem which forbids Kt and Kt,t,t together.</div>

    Tags:

  • Sung-Pil Hong (홍성필), Approximability of a batch consolidation problem
    Approximability of a batch consolidation problem
    Sung-Pil Hong (홍성필)
    Dept. of Industrial Engineering, Seoul National University, Seoul, Korea.
    2008/11/14 Fri, 4PM-5PM
    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.
    Tags:

Monthly Archives