Computing Strong Bounds in Combinatorial Optimization

24th February 2014, 3.00pm (AEDT)

Speaker's Name:

Hans Mittelmann

Speaker's Institution:

School of Mathematical and Statistical Sciences, Arizona State University

Title of Seminar:

Computing Strong Bounds in Combinatorial Optimization

Host Institution:

University of Newcastle

Time and Date:

Monday 24th February 2014, 3.00pm (AEDT)

Seminar Abstracts:

As is well-known semidefinite relaxations of discrete optimization problems can yield excellent bounds on their solutions. We present three examples from our collaborative research. The first addresses the quadratic assignment problem and a formulation is developed which yields the strongest lower bounds known for larger dimensions. Utilizing the latest iterative SDP solver and ideas from verified computing a realistic problem from communications is solved for dimensions up to 512.

A strategy based on the Lovasz theta function is generalized to compute upper bounds on the spherical kissing number utilizing SDP relaxations. Multiple precision SDP solvers are needed and improvements on known results for all kissing numbers in dimensions up to 23 are obtained. Finally, generalizing ideas of Lex Schrijver improved upper bounds for general binary codes are obtained in many cases.

Seminar Convener

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support:

This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.