New answers tagged

1

This is feasible to compute in fairly fast (polynomial) time with linear programming. This problem seems like a poster problem for linear programming where you specify a set of equalities and inequalities, e.g. tomato between 0 and 100 grams, apple between 0 and 100 grams and then if each gram of a tomato has 1 mg of vitamin X and each gram of an apple has 2 ...


5

One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}_{ij} = x_i x_j$ (the vectors have length $k^2)$. We have $$ \langle \hat{x}, \hat{y} \rangle = \sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2. $$ Therefore if you know the minimum inner product, you can solve OV. It remains to ...


3

Run a recursive procedure which keeps track of which elements appeared so far. If there are $k$ elements which haven't appeared so far and only $k$ positions left, choose one of them. With some care, you can convert the recursion to an iteration, if you so wish.


0

For the version where every clause must have exactly $k$ literals: There are ${n \choose k} 2^n$ possible clauses. (Why? Because you must choose exactly $k$ of the variables to appear in the clause, and then for each variable, you choose whether it appears negated or not.) A formula is obtained by choosing some subset of those possible clauses. So, the ...


0

There is a straightforward dynamic programming algorithm. You only need to know, for each $i,j$, the length of the shortest path to $(x_i,y_j)$ that covers the first $i$ points, and the length of the shortest path to $(x_j,y_i)$ that covers the first $i$ points. I'll let you discover why that suffices. You should be able to take it from here. See our ...


1

I'm not sure where Yuval got his formula from but when trying to replicate it I got a bit lost so I will share with you what I found. You can naively calculate the number of 4 cycles using $$\text{Tr}(A^4)=\sum_{ijkl}A_{ij}A_{jk}A_{kl}A_{li}$$ which you can read as "test if vertex $i$ is connected to vertex $j$, vertex $j$ is connected to vertex $k$ etc....


Top 50 recent answers are included