-
Linkage
- Real-world application of square packing: Packing ten quart bottles in a milk crate slightly larger than a \(3\times 3\) packing.
-
Congratulations, Dr. Patris!
I participated today in the successful Ph.D. defense of Nikolas Patris, a student of my newly-tenured colleague Ioannis Panageas. Nikolas has been working on problems of learning Nash equilibria of games and more generally finding saddle points of smooth functions, a crossover area between theoretical computer science and machine learning. His results are theoretical but his papers on them are in machine learning conferences:
-
Linkage
-
The degree of Fibonacci heaps
The Fibonacci heap is a priority queue data structure in which finding and removing the top-priority item takes logarithmic time (like a binary heap) but reprioritizing items to have higher priority takes only constant time, under amortized time analysis. This property is useful for speeding up the time complexity of algorithms including Dijkstra’s algorithm for shortest paths and Jarník’s algorithm for minimum spanning trees, so that they take logarithmic time per vertex and constant time per edge.
-
Linkage
-
Cubic salespeople revisited
Good news: Email from Knuth. Bad news: It begins “is there a bug in your paper?” The paper in question is “The traveling salesman problem for cubic graphs” (WADS 2003 and JGAA 2007). Of course the bug report is accurate, but fortunately it can be easily patched.
-
Linkage
-
H-trees are not trees
A sheet of a4 paper has aspect ratio \(1:\sqrt2\). This means you can crease it along the shorter of its two midlines to get two rectangles with the same aspect ratio (of a5 size) and continue in the same way recursively.
-
Linkage
-
Linkage with plum blossoms
…except they turn out not to be plum blossoms after all; see below.
subscribe via RSS