| DATE: | Friday, May 9th 2003 |
| TIME: | 2:00 PM - 4:30 PM |
| PLACE: | McConnell 103 |
| SCHEDULE: | ALGORITHM SEMINAR DAY |
|
10:00 - 10:30 Ryuhei MIYASHIRO 10:30 - 11:00 Hiro SAITO 11:00 - 11:15 --- coffee break --- 11:15 - 11:45 Hidetoshi NAGAI 11:45 - 12:15 Yuichiro MIYAMOTO | |
Ryuhei MIYASHIRO
Title: Home-Away Table Feasibility Problem
Speaker: Ryuhei MIYASHIRO (University of Tokyo)
Abstract:
In sports scheduling, a tournament organizer often need to construct a
schedule under given home-away assignment. "Home-Away Table Feasibility
Problem" determines whether given home-away assignment can be completed
into a schedule. In this talk, we consider this problem, and propose a
necessary condition for a feaible home-away table. We introduce a theorem
about the necessary condition, and show that the proposed condition
characterizes a feasible home-away table in a special case.
Hiro SAITO
Title : A polyhedral approach to Hub Location Problems.
Speaker : Hiro
Saito (University of Tokyo)
Abstract :
Hubs are switching facilities for
transportation in an airline network or a postal delivery system, etc. The
problem that designs a hub-and-spokes network is known as the Hub Location
Problem (HLP). In this talk, we investigate a polytope related to the
feasible region of (HLP). We show some polyhedral aspects of a mixed
integer programming formulation. Furthermore, we propose a cutting plane
method employing new facets. We also show the strength of the cuts through
computational experiments.
Hidetoshi NAGAI
Title: A simplicial branch-and-bound algorithm
for a production-transportation problem
with concave production cost
Speaker : Hidetoshi NAGAI (University of Tsukuba)
Abstract:
This talk deals with a production-transportation problem involving
nonseparable concave production cost and linear transportation cost, which
is a nonconvex network optimization problem. Although studies have been
made on the case of separable concave production cost, there exists no
algorithm to solve the problem with nonseparable case efficiently. Thus we
present a branch-and-bound based algorithm for this problem and show
computational results. The proposed algorithm solves the problem with
integral arc capacities in finite time. (This is a joint work with
Takahito KUNO.)
Yuichiro MIYAMOTO
Title: Simple Algorithm for Channel (Frequency) Assignment Problem
Speaker : Yuichiro MIYAMOTO (Sophia University)
Abstract:
In this talk, we deal with a channel (or frequency) assignment problem
that is an extension of the (vertex) coloring problem. We discuss a simple
approximation algorithm for special cases: an input of the instance is an
extension of unit disk graph without it's embedding.