2002-26: An Algorithm for Dualization in Products of Lattices

DIMACS TR: 2002-26

An Algorithm for Dualization in Products of Lattices

Authors: Khaled M. Elbassioni

ABSTRACT
Let $\cL=\cL_1\times\cdots\times\cL_n$ be the product of $n$ lattices, each of which has a bounded width. Given a subset $\cA\subseteq\cL$, we show that the problem of extending a given partial list of maximal independent elements of $\cA$ in $\cL$ can be solved in quasi-polynomial time.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-26.ps.gz

DIMACS Home Page