Seminar in Optimization (Spring 2010)

Date and Place	Speaker	Title	Abstract
26/03/10	Tarikul Sabbir	An Algorithmic study of Tree Decomposition(and Tree Width) and it's application on optimization problems	In graph theory, a tree decomposition of a graph is a measure of how much a graph resembles a tree. And the treeWidth measures the number of graph vertices mapped onto any tree node in an optimal tree decomposition. Many NP-hard graph problems can be solved in polynomial time for graphs with bounded/restricted treewidth. There are Several heuristic algorithms to find tree decompositions as well as tree-width. Some of heuristics are discussed in detail. This tree decomposition technique can also be applied to find (almost) optimal solutions for many optimization problems. In this context a dynamic programming framework is used on tree decompositions(under work in progress) of to solve facility location optimization problems like P-median and Covering problem on the original graphs. The time bound of the given algorithm is explained and on a closing note the potential ideas for improving the time bound are also discussed.
05/03/10	Mahmudul Hasan	DSJM: A software toolkit for Direct Determination of Sparse Jacobian Matrices	Packing the nonzero elements of a sparse Jacobian matrix in fewer column groups can gain significant performance improvement in Finite Differencing and Forward Automatic Differentiation methods. If $B\in \Re^{m\times p}$ is obtained via finite difference approximation or forward automatic differentiation, we can directly determine the jacobian $A\in \Re^{m\times n}$ using the partitioning matrix $S\in \Re^{n\times p}$, where $AS = B$, provided that the sparsity pattern of $A$ is a priori known. DSJM, a software toolkit written in C++, has been developed to provide some well-known as well as new partitioning algorithms for large sparse matrices. The heuristic algorithms used in the software can be explained from a graph coloring point of view. The relation of Zykov Tree with a coloring heuristic is also discussed.
29/01/10	Robert Benkoczi, Department of Mat/CS, University of Lethbridge	The parametric search method in optimization	Parametric search is an ingenious method to solve an optimization problem that generalizes the approach based on feasibility tests. For some optimization problems, a feasibility test is easier to solve since the test doesn't ask for the optimal solution to the problem, but whether the optimal solution is larger or smaller than a given test value. This presentation should be accessible to graduate and 3rd & 4th year undergraduate students.
01/02/05	Sangita Bhattacharjee Graduate Student & Research Assistant Department of Math & Computer Science	A Primal-Dual algorithm for Maximum-Charge Problem with capacity constraints	Maximum charge problem is a generalization of Maximum Cardinality Matching Problem, a well known problem in graph theory. Given a graph with arbitrary positive capacities assigned on every vertex and every edge the goal is to maximize the total amount of charge on edges subject to the capacity constraints. We use the primal-dual approach for the maximum charge problem. We characterize the optimal solution to the dual of the restricted primal(DRP)and give a combinatorial algorithm for solving the DRP.