# Tag Info

3

Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.

3

1-IN-3SAT is an NP-complete variant of 3SAT in which the goal is to determine whether some assignment satisfies exactly one literal per clause. We can convert an instance of 1-IN-3SAT (even without the restriction on the number of literals per clause) to an equivalent instance of quadratic programming in which all the variables are constrained to be non-...

3

I could do QuickSelect (j - i) times to get all the elements Overkill. Two calls to QuickSelect and one linear pass are sufficient.

2

A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though. Tractability of convex problems essentially boils down to being able ...

2

You are essentially asking this: "Given a graph $G=(V,E)$ where each vertex in $V$ denotes a person and each edge $(u,v) \in E$ means that $u$ is incompatible with $v$, what is the minimum number of colors required to color the vertices of $V$ such that no edge in $E$ has both endpoints of the same color?" In other words, given any graph $G$ (which can ...

2

I assume that in the $k$ bucket case, each rock has up to $k$ colors (buckets) associated with it, which are the ones it can be put into. It seems to me that a polynomial time algorithm can be obtained by reduction to a minimum-cost flow problem, which can be solved in polynomial time. Create a network with $k + n + 1$ nodes: $n$ rock nodes, $k$ bucket ...

2

Depending on the input values the following strategy might work: keep an array $C$ of $10^6$ elements where $C[i]$ will store the number of times number $i$ appears in the elements of the input array that have already been processed. Initially $C$ is identically 0, then you consider the elements $A_i$ one at a time. When you are processing the $A_i$ you can ...

2

This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $n_1$ at the end. Observation: after this process is done all ...

1

The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging. Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible ...

1

Yes, this is absolutely still considered a genetic algorithm. In fact, it is quite common to experiment with various strategies of obtaining an initial population. As you say, it is reasonable to start with a completely random population unless you have a reason to try something else. Whether this is a good way to go is anybody's guess, really. It depends ...

1

The relative performance of different optimization algorithms depends a lot on the particular function you are minimizing. We certainly can't tell you whether it is really that good for your particular function without knowing what specific objective function you are looking at, but it certainly seems possible to me. There are some functions where Newton's ...

1

I won't go into the details of your specific case but try to answer the general problem. In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows: Create a partitioning of the initial $n$ input states into subsets. Your adapted function maps each of these ...

Only top voted, non community-wiki answers of a minimum length are eligible