Welcome to MathOverflow

Question

4

1

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.

Call a lattice nice if it is of the form $\mathbb{Z}$-span({$v_1, v_2, \dotsc, v_m$}), where all $v_i$ are nice. (Note: the $v_i$ are not necessarily linearly independent so $m$ could be larger than the dimension; although WOLOG $m \le \tbinom{n}{2}$.)

Is the following decision problem in P?

INPUT: a nice lattice and a vector $x \in \mathbb{Z}^n$
QUESTION: does the lattice contain a $y$ such that $y_i \ge x_i$ for all $i=1, \dotsc, n$?

Motivation and background:

in general lattices, the problem is NP-complete (via the unbounded knapsack problem)
if this problem lies in P, one can solve an interesting more general problem

A possibly interesting partial result would be to demonstrate any useful structure for nice lattices!

(I posted a flow formulation of the problem on cstheory)

edited Feb 24 2011 at 11:46

asked Feb 22 2011 at 13:28

Dave Pritchard
677●5●12

	Trivial comment. If we take $v_1=(1,-1,0, \dots, 0), v_2=(0,1,-1,0, \dots, 0), \dots, v_{n-1}=(0, \dots, 1,-1)$, then the $\mathbb{Z}$-span of all the $v_i$'s is in fact all integer vectors whose coordinates sum to zero. – Tony Huynh Feb 22 2011 at 14:53
	Not-as-trivial comment: There are at most finitely many vectors y which are both nice and greater than x (the sum of whose components must be at most 0). This can be transformed into finding integer solutions to a system of linear inequalities; if the transform went the other way, I think it would show the problem to be NP-complete. Gerhard "Ask Me About System Design" Paseman, 2011.02.22 – Gerhard Paseman Feb 22 2011 at 17:16
	Of course, there is the brute force approach: if the sum of the coefficients of x is -r, try the O(r^(n-1)) nice vectors above x and see which are in the desired lattice. Gerhard "Is There A Better Way" Paseman, 2011.02.22 – Gerhard Paseman Feb 22 2011 at 17:23
	Yes, your comments are valid. Tony, more generally than what you state, the problem becomes poly-time solvable if all of the nonzero entries form a chain under division (e.g., all 1s, 2s, 6s, 30s...) – Dave Pritchard Feb 24 2011 at 11:47

Domination in Nice Lattices

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.