bio | website | cs.ox.ac.uk/people/… |
---|---|---|
location | Oxford, United Kingdom | |
age | 51 | |
visits | member for | 4 years, 2 months |
seen | 1 hour ago | |
stats | profile views | 1,942 |
Feb 16 |
revised |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
added 58 characters in body |
Feb 16 |
revised |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
fixed the 2nd reference |
Feb 16 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
I'll blame my wife - I never played Sokoban myself ;) |
Feb 16 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
how are you going to do 1) in polytime? |
Feb 15 |
answered | Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another |
Feb 15 |
answered | Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another |
Feb 15 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
yes, chip="фишка" |
Feb 15 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
It seems to be a computationally hard problem, in the sense that every algorithm will need time exponential in $m$. |
Feb 15 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
IMHO it's better to formulate this in terms of $m$ chips placed on nodes of your digraph $G$, at most one chip on a node, and each move in this game, with the goal is to place chips on a fixed subset of "final" nodes, is to move a chip on a node $v$ to the other end $u$ of an arc $vu$, without violating the condition that there is at most one chip on a node. |
Feb 15 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
it's not clear what are moves allowed. Are you moving the 'init_j' vertices at the same time? By the way, "wave algorithm" seems to be what is called "breadth-first search" in English. |
Feb 10 |
answered | complexity of finding optimal matchings of given fixed size |
Feb 10 |
comment |
Find a convex hull that contains given points?
the idea is to choose pairs $\pm v_i$ of maximal norm, IMHO... |
Feb 10 |
comment |
basics of classification of trilinear forms (when is it non-discrete)
MathSciNet shows 2 references on the paper you cited, have a look! |
Feb 10 |
comment |
basics of classification of trilinear forms (when is it non-discrete)
In the case $n_1=n_2=n_3$, isn't it the same as classification of non-associative algebras? That was worked on a lot by A.Albert, etc. |
Feb 10 |
comment |
Mclaughlin Graph
You most probably don't have AtlasRep installed. Try gap> LoadPackage("AtlasRep"); (i.e. one ';', not two - which suppresses output). I guess it will return 'fail'. |
Feb 4 |
comment |
Factorization of bivariate polynomial
well, there are branches of mathematics, commutative algebra, and algebraic geometry, which, among other, deal with questions like this. In general, bivariate polynomials (with coefficients in an infinite field) almost never factor. |
Jan 19 |
comment |
Generating function of a regular language
Aren't you are looking for what is known "transfer matrix method" in enumerative combinatorics? see e.g. Sect.4.7 in vol. 1 of R.Stanley book Enumerative Combinatorics |
Jan 12 |
revised |
Over which fields are symmetric matrices diagonalizable ?
proper matrix typesetting |
Jan 11 |
comment |
A sum related to the Johnson association scheme
Well, it might be it - no simpler formula. Often this is the case, e.g. check out recent work of A.Schrijver and his collaborators on improved bounds for codes, such as arxiv.org/abs/1005.4959, homepages.cwi.nl/~lex/files/codes.pdf. However, often sums like yours come up as entries of a certain matrix, and this matrix might have a reasonably nice $LU$ decomposition. E.g. in your case $L$ might be having entries ${n \choose k}$. |
Jan 10 |
comment |
Largest permutation group without 2-cycles or 3-cycles
oops, you're right. I somehow didn't think straight enough when I realized that the example in the question can be improved. :-) |