Seminars in Computing and Software

Upcoming seminars are listed below.
If you wish to look a previous year, select it from the option list and click on the Submit button.

Upcoming Seminars

Computational and Combinatorial Aspects of Linear Optimization

Zhongyan Guan
PhD Thesis Proposal Defense

Date: 2017-06-26     Time: 09:30:00     Room: ITB 225


Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few
of the areas operations research is concerned with. In many cases, these problems can be
formulated or approximated as linear optimization problems, which involve maximizing or
minimizing a linear function over a domain defined by a set of linear inequalities. The simplex
and primal-dual interior point methods are currently the most computationally successful
algorithms for linear optimization. While the simplex methods follow an edge path, the interior
point methods follow the central path. The algorithmic issues are closely related to the
structure of the associated feasible region formed by all feasible solutions.

Finding a good bound on the maximal edge-diameter of a polytope in terms of its dimension and
the number of its facets is historically closely connected with the theory of the simplex
method, as the diameter of the associated feasible region is a lower bound for the number of
pivots required in the worst case. Considering bounded feasible regions whose vertices are
rational-valued, the proposal investigates a similar question where the number of facets is
replaced by the grid embedding size.

Sponsor(s): CAS
Contact(s): Antoine Deza

© 2006 McMaster University  |   1280 Main Street West  |   Hamilton, Ontario L8S4L8  |   905-525-9140  |   Contact Us   |   Terms of Use & Privacy Policy