Impact
~25k
people reached
- 0 posts edited
- 1 helpful flag
- 779 votes cast
Oct
27 |
comment |
Group Travel Salesman Problem
What are your assumptions on the distances? WIthout any assumptions it is NP-hard to approximate TSP with any polynomial time computable function as approximation factor. For the Euclidean case you might want to look at link.springer.com/chapter/10.1007/11523468_90 |
Oct
26 |
comment |
Group Travel Salesman Problem
The paper Approximation algorithms for the geometric covering salesman problem, Esther M. Arkin and Refael Hassin, Discrete Applied Mathematics 55(3), 197-218 (1994), dx.doi.org/10.1016/0166-218X(94)90008-6 contains approximation results for graphs with geometric structure. |
Oct
21 |
revised |
On the dependence on $\epsilon$ in Dvoretzky's theorem
added arxiv reference |
Oct
21 |
suggested | rejected edit on On the dependence on $\epsilon$ in Dvoretzky's theorem |
Oct
21 |
revised |
On the dependence on $\epsilon$ in Dvoretzky's theorem
added 240 characters in body |
Oct
21 |
answered | On the dependence on $\epsilon$ in Dvoretzky's theorem |
Oct
21 |
answered | Two fold optimization: is there an established approach for this kind of problem? |
Sep
24 |
comment |
Integers in Boxes Problem
The journal version (Average case analysis of greedy algorithms for optimisation problems on set systems, Theoretical Computer Science 145 (1995), 267-298) is available here: basepub.dauphine.fr/xmlui/bitstream/handle/123456789/3978/… |
Sep
23 |
revised |
Integers in Boxes Problem
added tag co.combinatorics |
Sep
22 |
suggested | approved edit on Integers in Boxes Problem |
Sep
18 |
awarded | Enlightened |
Sep
18 |
awarded | Nice Answer |
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 |