All Questions
Tagged with approximation-algorithms heuristics
8 questions
1
vote
1
answer
186
views
Practical/heuristic algorithm for multi set-cover
Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...
- 791
6
votes
2
answers
396
views
Finding smallest context free grammar that generates a set of sets
Are there any results known about the size of smallest context free grammar that generates a set of sets?
That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
- 338
3
votes
0
answers
142
views
Complexity of minimizing monotone arithmetical formulas
Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(...
- 338
1
vote
1
answer
108
views
Approximations for the Stable Fixtures Problem
I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
- 113
4
votes
0
answers
160
views
Find index set partition that has large projections
I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$...
- 12.4k
8
votes
3
answers
402
views
Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$
How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + ...
- 323
7
votes
1
answer
510
views
Does this bin packing problem have a name?
My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a ...
- 1,520
5
votes
1
answer
168
views
Local Smoothness vs optimisation in combinatorial problems
Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation. What is meant precisely by local smoothness is often left out, but ...
- 835