- From: Oriol Brufau via GitHub <sysbot+gh@w3.org>
- Date: Wed, 11 Apr 2018 09:18:12 +0000
- To: public-css-archive@w3.org
I know very little about grid, but the problem in https://github.com/w3c/csswg-drafts/issues/2356#issuecomment-379206560 looks like an LP (unless you want to consider the lengths to be an integral number of pixels, then it's ILP and much more hard). Effectively the simplex algorithm is the common approach. The linear inequalities define a polytope which is the feasible region among which you want to find the point where the objective function is optimal. This solution may not be unique, but (if the problem is feasible) a vertex of the polytope will be one of these solutions. Simplex starts at some vertex and then keeps iterating contiguous vertices, moving in the direction of the maximum slope of the objective function. This means that in common cases, the algorithm will be fast. The downside is that a polytope has an exponential number of vertices, so the worst-case is exponential. Instead of simplex, there are interior point algorithms which are guaranteed to be polynomial in the worst case, but they may be slower for common cases. At university I wasn't taught how these algorithms actually work so probably they are much more complex to implement than simplex, which is not difficult (as an exercise I implemented it in matlab in no more than 100 lines, I think), just a bit tricky because you want to avoid cycles and various other subtleties which can make it go wrong in edge cases. There are solvers specialized in this kind of problems, but usually they have commercial licenses. So yes, a post-processing step in the grid algorithm might be a better option. -- GitHub Notification of comment by Loirooriol Please view or discuss this issue at https://github.com/w3c/csswg-drafts/issues/2356#issuecomment-380385419 using your GitHub account
Received on Wednesday, 11 April 2018 09:18:45 UTC