Skip to main content
4 votes
Accepted

Maximizing GCD of a variable set of numbers

Input: $s$ = sum of the numbers, and $m$ = the number of numbers. Output: the greatest possible $d$ such that $GCD(a_1,\dots,a_m)=d$ and $\sum_{i=1}^ma_i = s$. Observe: Let $b_i = a_i / d$. Then $c:=\...
Benjamin Wang's user avatar
3 votes

Maximizing GCD of a variable set of numbers

You can solve the problem via dynamic programming (DP) as follows. Let value function $V(m,M,p)$ be the maximum GCD of $m$ distinct positive integers $\le p$ that sum to $M$. By conditioning on the ...
RobPratt's user avatar
  • 47k
3 votes
Accepted

How to prove that this binary optimization problem can be decomposed into two subproblems?

Consider optimization problem $(1)$: $$\min_{x,y} f(x) + g(y)$$ subject to $(x,y) \in X \times Y$. Consider optimization problem $(2)$: $$\min_x f(x)$$ subject to $x \in X$. and optimization problem $...
Siong Thye Goh's user avatar
2 votes
Accepted

Finding the set of solution to a linear sums problem

I don't think there is a general efficient algorithm for your problem. If you take DL=DH=0 then your basically have the subset sum problem, which is NP-complete (https://en.wikipedia.org/wiki/...
Matthew Spam's user avatar
2 votes

Partition algorithm for minimal summation

This is my answer: This problem is strongly NP-hard: 3-partition problem is a special case with $a_i = 0$ for all $i$. In practice, I would try using integer programming solvers. Example formulation: $...
pcpthm's user avatar
  • 141
2 votes
Accepted

Determine the minimal tiling, allowing for both overhang and overlap, from a small shape to a larger one.

You can solve this set cover problem via integer linear programming as follows. Let $S$ be the set of possible cells for sprinklers. For $(i,j)\in S$, let binary decision variable $x_{ij}$ indicate ...
RobPratt's user avatar
  • 47k
1 vote
Accepted

Consecutive binary block in MIP modeling with variable length

For simplicity, I'll omit the $v$ index. You want to enforce $X_t=1 \iff A \le t \le A+P$. You can do so as follows, without introducing additional variables: \begin{align} A - t &\le (t_\max-t)(...
RobPratt's user avatar
  • 47k
1 vote

Maximizing GCD of a variable set of numbers

In your special case the sum equals 8 x 3 x 11, so the gcd has no other prime factors. 5 different numbers, all multiples of the gcd, are at least 15 x gcd, so gcd <= 264/15, so gcd <= 17. All ...
gnasher729's user avatar
  • 10.2k
1 vote
Accepted

Is there any algorithm to calculate this ranking method quickly?

This problem goes by several names: rank aggregation, minimum cost feedback arc set, linear ordering problem, Kemeny-Young method, minimum violations ranking. You can solve the problem via integer ...
RobPratt's user avatar
  • 47k
1 vote
Accepted

Question about a property of the integer-hull

Let $q\in Q_I$ and $e\in E_I.$ We can write them as $$q=\sum_{k=1}^{K}\lambda_{k}q_{k}$$ and $$e=\sum_{j=1}^{J}\mu_{j}e_{j}$$ where $q_{k}\in Q\cap\mathbb{Z}^{n},$ $e_{j}\in E\cap\mathbb{Z}^{n},$ $\...
prubin's user avatar
  • 5,178
1 vote
Accepted

Correctly understand the implication of approximation ratio for the set cover problem?

I think you may be confusing "cannot approximate all instances unless $P=NP$" with "cannot approximate any instance unless $P=NP$". The statements in the Wikipedia entry should be ...
prubin's user avatar
  • 5,178

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