Polynomial-Time Maximisation Classes: Syntactic Characterisation
Prabhu Manyem (The University of Ballarat)
MSI Computational Mathematics (formerly AdvCom) Seminar SeriesDATE: 2006-11-13
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman Seminar Room G35
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as f{P, NP, L and NL}. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper, we characterised the optimisation versions of f{P} via expressions in second order logic, using universal Horn formulae with successor relations. In this talk, we look at the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound f{NP} (not just f{P}) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application -- we show that the Bin Packing problem with online and item-size constraints can be approximated to within a $Theta(log n)$ bound, by providing a syntactic characterisation for this problem.
BIO:
Prabhu Manyem obtained his BS and MS degrees at the Indian Institutes of Technology, and his PhD (Discrete Optimisation), with a minor in Computer Science, at North Carolina State University, Raleigh, NC in 1996. After working in the US industry for three years, he joined the University of South Australia at Adelaide in 1999 as a Research Fellow. In February 2005, he moved to the University of Ballarat. His interests are in Complexity, Approximation Algorithms and Discrete Optimisation.
