McGill University - School of Computer Science

Algorithms Seminar 2003

Everybody is welcome!

DATE: Friday, May 9th 2003
TIME: 2:00 PM - 4:30 PM
PLACE: McConnell 103
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

Title: Home-Away Table Feasibility Problem
Speaker: Ryuhei MIYASHIRO (University of Tokyo)
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.

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

Title: Simple Algorithm for Channel (Frequency) Assignment Problem
Speaker : Yuichiro MIYAMOTO (Sophia University)
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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer(at)cs(dot)mcgill(dot)ca. 
Web Address: