All Questions
10
questions with no upvoted or accepted answers
5
votes
0
answers
121
views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
- 51
2
votes
0
answers
84
views
Difference Sets
suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$
where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct.
We calculate the differences as: $$d=p_i-p_j\mod ...
- 3,989
1
vote
0
answers
30
views
Can we find a proper $\phi$ so that maps each interval to its center?
For a compact interval $[0,1]$, we divide it into $N^{1/3}$ subintervals with length $N^{-1/3}$. Define a map $\phi: [0,1]\mapsto [0,1]$ maps each subintervals to its center.
For example, let $X\sim ...
- 1,514
1
vote
0
answers
294
views
Algorithm to find maximum sum over weighted overlapping intervals
Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
- 173
1
vote
2
answers
641
views
Number of combinations of increasing tuples given their sum
A tuple is represented by
$(a_i,a_{i-1},...,a_1)$ where $a_i<a_{i-1}$ and $i \in \{2...N\}$
So, valid tuples are $(1,2,3,4)$ and $(2,5,9,41)$
You are given the sum of these tuples
$a_i + a_{i-1}...
- 33
0
votes
0
answers
36
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
0
votes
0
answers
28
views
Ordering of points based on their relative positions (limited info incl. errors)
I am currently working on a problem which I assume mathematicians have already solved.
Setup: I have $N$ people standing in a line. Each of them is assigned with a different number between $1$ to $N$. ...
0
votes
0
answers
35
views
Runtime Complexity of Memoization
I am struggling to analyze the runtime complexity of the following algorithm formally:
Given a string s and a dictionary of words dict(wordDict), add spaces in s to
construct a sentence where each ...
- 201
0
votes
0
answers
34
views
Expected size of a set with iterative probabilistic growth
We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches.
We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At ...
-1
votes
1
answer
93
views
Algorithm to order and partition a set of of (n,m) pairs with constraints.
I ran into this problem while looking at Google API distance matrix service.
Say you have a collection of a few million (origins, destinations) unique pairs/2 column table like (address, zip) for ...
- 11