New answers tagged

1 vote
Accepted

Efficient algorithm to count number of intersections of n sets

Assuming you really need the number for all pairs of sets and hearing that we are thinking of users in communities you could use the following algorithm which relies on the idea that the the average ...
user avatar
  • 1,106
1 vote
Accepted

A lower bound for the makespan of heterogenous fog nodes

Under the assumption that $EXT(N_i) = \mathit{MinMakespan}$, $$ \sum_{k \in N_i \mathit{Tasks}} \mathit{length}(T_k) = \mathit{MinMakespan} \times \mathit{CPUrate}(N_i). $$ Therefore $$ \sum_k \mathit{...
user avatar
2 votes
Accepted

Algorithm to compute cheapest path between two pixels in an image

That sounds like a variant of grid pathfinding(mostly used in game). Generally, if your cost function has a good heuristics, A star will give you an optimal solution with least time cost. But space ...
user avatar
  • 93
0 votes

Solving linear programming problem with mixed type of constraints

You always need an initial solution. If you don't have one, you create another problem to get the initial solution. In your case: Imagine you don't ship enough cars. Customer 1 misses $x_7$ and ...
user avatar
  • 25.2k
1 vote

Compute a commutative and associative operation on n-2 arguments efficiently

(Motivation: let $h = n/2$. Given $f_{ih} = f(x_i\dots x_{h-1}) \text{ and } f_{hj} = f(x_h\dots x_j)$ (precomputed in about $n$ evaluations of $f$), $f(x_{i+1}\dots x_{j-1})$ can be computed as $f(f_{...
2 votes
Accepted

Compute a commutative and associative operation on n-2 arguments efficiently

(1) You can compute $f(x_1,\dots,x_{i-1})$ for all $i$ with $n-2$ calls to $f$. (Simply iterate over $i:=1,\dots,n$.) (2) Then, using (1), you can compute $f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1})$ ...
user avatar
  • 141k
0 votes

Compute a commutative and associative operation on n-2 arguments efficiently

Count how many times each $x_i$ occurs in the argument list. Suppose $X_1$ is the set of $x_i$ that occur once, $X_2$ is the set of $x_i$ that occur twice, ..., $X_m$ is the set of $x_i$ that occur $m$...
user avatar
  • 115
2 votes
Accepted

Complexity of the partition problem with additional constraint

As you mentioned the first problem can be reduced to the second one by replacing each positive integer $a_i\in S$ by a paired $(a_i,0)$. Moreover, the second problem can be reduced to the first one by ...
user avatar
2 votes

Choosing a subset to maximize the minimum distance between points

This problem is known as the MaxMin Diversity Problem (MMDP). It is known to be NP-hard. However, there are algorithms for giving good approximate solutions in reasonable time, such as this one. I'm ...
user avatar
  • 121
1 vote

Printing an array using recursion

It takes most (when not all) compilers more time to call a function, then to jump back with the programmcounter. (The number that indicates which line gets executed.) When a function gets executed, ...
user avatar
  • 11

Top 50 recent answers are included