bio | website | |
---|---|---|
location | Newcastle, Australia | |
age | 34 | |
visits | member for | 4 years, 7 months |
seen | 2 hours ago | |
stats | profile views | 1,350 |
Aug
10 |
revised |
Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)
added 120 characters in body |
Aug
8 |
answered | Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns) |
Jul
31 |
comment |
Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)
The problem can be written as follows: Minimize $\sum_{i=1}^nx_i$ subject to $x_i\geqslant y_{ij}$ for $i\in\{1,\ldots,n\}$, $j\in\{1,\ldots,C\}$, $\sum_{i=1}^n\sum_{j=1}^Cy_{ij}z_{ijk}=b_k$ for $k\in\{1,\ldots,m\}$, $\sum_{k=1}^mz_{ijk}=1$ for $i\in\{1,\ldots,n\}$, $j\in\{1,\ldots,C\}$, $z_{ijk}\in\{0,1\}$ for all $i,j,k$ and $y_{ij}\geqslant 0$ for all $i$, $j$. |
Jul
31 |
comment |
Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)
$(b_1+\cdots+b_m)/C$ is a trivial lower bound. For the given instance this gives 452. Cutting $1100=4\times 275$, $540=3\times 180$ and $170=170$, we can achieve $275+180=455$, which looks optimal to me. |
Jul
24 |
revised |
A question of Erdős
added 215 characters in body |
Jul
24 |
answered | A question of Erdős |
Jul
21 |
answered | Dividing the edges and diagonals of a polygon among disjoint sub-polygons |
Jul
8 |
revised |
What is known about the complexity of this covering problem?
added 101 characters in body |
Jul
8 |
revised |
Maximum cardinality general factor of a graph
added tag co.combinatorics |
Jul
8 |
suggested | approved edit on Maximum cardinality general factor of a graph |
Jun
16 |
awarded | Organizer |
Jun
16 |
revised |
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
added tag co.combinatorics |
Jun
16 |
suggested | approved edit on Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling? |
Jun
16 |
revised |
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
deleted 63 characters in body |
Jun
16 |
revised |
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
added 396 characters in body |
Jun
16 |
revised |
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
deleted 105 characters in body |
Jun
16 |
answered | Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling? |
May
14 |
awarded | Nice Answer |
May
11 |
comment |
What is known about the complexity of this covering problem?
@RupeiXu Yes, it means that for every vertex $v\in V\setminus X$ the intersection of $X$ and the neighbourhood of $v$ is either empty or has at least size 2. |
Apr
22 |
comment |
What is known about the complexity of this covering problem?
@DominicvanderZypen Yes. I can start the algorithm in the original post with a singleton $S=\{v\}$. If I get stuck then the complement of the final set is a critical set $\neq V$. Now let's do this for every start vertex $v\in V$. If we reach $S=V$ in each case it follows that every vertex is contained in every critical set, and therefore $V$ is the only critical set. |