1,757 reputation
716
bio website
location Newcastle, Australia
age 34
visits member for 4 years, 7 months
seen 2 hours ago

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.