Booked my stay at Edinburgh for OP26. Will be arriving on Saturday (30th of May) for ample time to hike in the beautiful landscape. Maybe Ben Nevis, maybe something closer and slightly less challenging.
As I travel alone, feel free to text me if you wanna join.
For a decade it was open whether Frank-Wolfe's O(1/√ε) rate on strongly convex sets is tight. We show it is: Ω(1/√ε), even for a simple quadratic on a unit ball.
So much good stuff here, but I would like to highlight the benefit of practicing. When you know the presentation by heart, you don’t need to spend cognitive effort remembering what to say. That frees attention for connecting to the audience. You'll learn what works and not, they'll stay engaged.
The frame freeze and overlay gives a really cool effect, but not a fan of handwriting in digital media.
While I haven't finished processing the linked paper, I believe the idea is to limit the set of inputs and give room for error in the output. This is what brings polynomial complexity. The impressive part is when this is achievable by very mild assumptions (satisfied in practice).
www2.mathematik.tu-darmstadt.de/~disser/pdfs...
I seem to recall the solution of a knapsack problem being embedded in how many times some columns entered the basis for some specific simplex method, so maybe the bridge for such a result has already been established @sophie.huiberts.me ?
I wonder whether something similar can be done in the field of NP-hard problems, to obtain polynomial complexity results by similar (algorithmically mild) assumptions on scaling, perturbations, etc. This would shed light on why we are able to solve knapsack and TSP problems to very high dimension.
Great article, and I do like that you address my initial thoughts immediately: "One canonical approach...". Is it common to only have an exam period of 6 days though? That 7 day schedule looks at lot more attractive.
That is a much harder question I think. Reminds me of the largest sofa that you can move around a corner problem.
Don't forget to ignore posts with foul language. That really removes a lot of junk.
If yes, I would try adding a supernode (connected to all) and require flow conservation, an inflow of at least one for the closed neighborhood (setminus supernode) of each node, and minimize the number of used edges. For n=8, this is still a rather small problem for MIP solvers.
Is this just one more than the shortest snake needed to visit the closed neighborhood of each node at least once? 🤔
Oh, that’s so satisfying! I stopped at the 4-norm ball thinking I had the solution as it fits the hole like a pot lid (has a perfect circle as an intersection).
Consider contributing to epoch.ai/frontiermath. As no sizes are given, it is kinda implicitly assumed that "every p norm ball" also includes every size. And with this, you probably want to rule out infinite packings with gap approaching zero, let alone trivial covers of the hole.
Unfortunately, it seems there is quite a theoretical gap between circles and hula hoops: link.springer.com/article/10.1...
So I should be able to fill space with hula hoops without bending them out of shape -- thinner the hoops, better the cover? Sounds impressive.
I have only tried for small code snippets and can't say its making me more productive, but it's definitely interesting and stimulates another skill set.
Having a strong background in programming, I find that code generation is a great exercise for peer reviewing. It starts with the naive approach, and then you iteratively refine it by corner case handling, performance tuning and simplification. Not unlike how some educational books are written.
It seems to me they distribute from their strongest military positions to minimize operational risk, using small boxes (=frequent revisits) to get better tracking of where it goes.
Has anyone built enough intuition for Gomory Cuts to dare explain when they are excellent and when they are terrible in this game?
The quote “I would have written a shorter letter, but I did not have the time” comes to mind.
Nice goal. I may object that the floors and ceils are a bit hard to distinguish, or is it just me?
⌊|⌈⌉|⌋|⌊
I haven’t tried it yet, but the new kid on the block is Typst with Hayagriva for citations. Categories seems to make sense:
github.com/typst/hayagr...
I like this. A 68% confidence interval around 10 is probably quite a good model for what people actually mean when they say 10 ± 1 and do the hand gesture.
10 ± 1 is
(a) the boolean expression "9 or 11",
(b) the set {9, 11},
(c) the interval [9, 11],
(d) an ambiguous operation that can't be used without context?
Consider the LP problem min{cᵀx : Ax=b, x≥0} with dual
max{bᵀy : Aᵀy≤c}. Adding Gaussian noise with std σ to all of A and c, the problem can be solved by a dual simplex method in O( 1/sqrt(σ) n^2.75 log(m)^1.75 ) pivot steps following the shadow vertex pivot rule. See arxiv.org/abs/2504.041....
Agreed, but it sparks an interesting question. What is the most difficult optimization problem which is simple to explain without math?
In November 1979, the NYT (🤮) writes of the then-new ellipsoid method that "the discovery may be applicable in weather prediction"
Does anyone know how LP would be used in weather prediction?
When you are so deep into OR you start thinking about injective functions as 'codomain packing'.. 😅
Let f: X → Y and consider the sets {f(x)} for each element x∈X. The function is injective/surjective/bijective if and only if these sets forms a packing/covering/partitioning of Y.