mmissoldtw ←
Management and Tech Notes342 posts
Management and Tech Notes avatar

Management and Tech Notes

@padlogk

Mgmt | Tech | Productivity posts. Catch-all of random thoughts.

◷ Joined January 2021▧ 125 Photos and videos
Management and Tech Notes avatar
Management and Tech Notes@padlogk·5h

Chained LK = iterated local search with LK as the descent and a double-bridge kick as the perturbation, accepting better-only. Warm starts make each iteration cheap. #algorithms #tsp Level 4 · Undergrad CS

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·13h

Chained LK by numbers: best tour 100 → double-bridge kick (115) → LK → 96, adopt it. Kick again → 110 → LK → 94. Worse results are rejected, so the best only drops. #algorithms #tsp Level 3 · High-school

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·Nov 14

Want the shortest route to visit your friends? Try every possible order and keep the best 🧭 Brute force always finds the perfect answer, just not quickly. #algorithms Level 1 · ELI5

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·Nov 14

Branch-and-cut is the exact frontier: Concorde proves optimal tours at 10⁴–10⁵ cities with comb, clique-tree and domino-parity cuts. Why it works so well is still open. #algorithms #tsp Level 6 · Researcher

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·Nov 13

Branch-and-cut is polyhedral combinatorics: the subtour polytope's LP value equals the Held–Karp bound (~1–2% off), and comb and clique-tree facets close the gap. #algorithms #tsp Level 5 · Graduate

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·Nov 13

TSP as an ILP (Dantzig–Fulkerson–Johnson 1954) has 2ⁿ subtour constraints. Branch-and-cut adds only violated ones, found by min-cut, and branches when stuck. #algorithms #tsp Level 4 · Undergrad CS

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·Nov 12

Branch-and-cut solves a relaxed puzzle, spots how the answer cheats, and adds a rule that bans just that cheat. When cutting stalls, it branches. That's how big TSPs get solved. #algorithms #tsp Level 2 · ELI10

Post attachment
Management and Tech Notes avatar
Management and Tech Notes@padlogk·Nov 11

Your quick answer cheats by drawing little separate loops? Add a rule: no little loops! 🔪 Branch-and-cut keeps slicing away cheats until the perfect trip remains. #algorithms Level 1 · ELI5

Post attachment