Jon Lee
On the number of solutions of the discretizable molecular distance geometry problem.
Tue, 10/12/2010 - 15:01 — SomNambulAuthors: Jon Lee, Antonio Mucherino, Leo Liberti, Benoit Masson, Carlile Lavor
Subjects: Discrete Mathematics
AbstractThe Generalized Discretizable Molecular Distance Geometry Problem is a
distance geometry problems that can be solved by a combinatorial algorithm
called ``Branch-and-Prune''. It was observed empirically that the number of
solutions of YES instances is always a power of two. We give a proof that this
event happens with probability one.The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions.
Mon, 06/07/2010 - 15:01 — SomNambulAuthors: Robert Weismantel, Shmuel Onn, Jon Lee, Lyubov Romanchuk
Subjects: Optimization and Control
AbstractWe consider the nonlinear integer programming problem of minimizing a
quadratic function over the integer points in variable dimension satisfying a
system of linear inequalities. We show that when the Graver basis of the matrix
defining the system is given, and the quadratic function lies in a suitable
{\em dual Graver cone}, the problem can be solved in polynomial time. We
discuss the relation between this cone and the cone of positive semidefinite
matrices, and show that none contains the other.Intractability of approximate multi-dimensional nonlinear optimization on independence systems.
Fri, 01/29/2010 - 16:01 — SomNambulAuthors: Robert Weismantel, Shmuel Onn, Jon Lee
Subjects: Optimization and Control
AbstractWe consider optimization of nonlinear objective functions that balance $d$
linear criteria over $n$-element independence systems presented by
linear-optimization oracles. For $d=1$, we have previously shown that an
$r$-best approximate solution can be found in polynomial time. Here, using an
extended Erd\H{o}s-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a
$\rho n$-best solution requires exponential time.
User login
