Combinatorial Optimization

What Hacker News says

1. eruFeb 2020
   Sounds like you would make a good mathematician.

   I had a very similar reaction to the much vaunted 'Algorithm Design Manual'. It was all fluff with not much substance.

   I found http://jeffe.cs.illinois.edu/teaching/algorithms/ pretty good for an overview over Algorithms.

   If you like something in a similar vein to TAOCP, the book 'Combinatorial Optimization' by Alexander Schrijver fits the bill. It teaches you everything you ever wanted to know and then some on the mathematics behind problems in P. Just like TAOCP it is also a detailed overview over known results. See https://homepages.cwi.nl/~lex/files/book.pdf for the list of contents.

   Show morethread
2. eruJun 2011
   Yes, I just went for something really basic to give an example of a semi-implicit indirect proof.

   I spent years of my life reading mathematics, so I do not trust myself to judge how hard a piece of mathematics is for outsiders. I find the proof cited is easy to read.

   About your addendum: You could have a look at Alexander Schrijver's "Combinatorial Optimization: Polyhedra and Efficiency". The interesting thing about its style is, that the author manages to make all lines require constant thought, while in most books there are really hard and really easy parts.

   Show morethread
3. eruFeb 2011
   I have a smart co-worker who also likes Skiena's Algorithm Design Manual. I found that book to fluffy, though. But then I enjoy books like "Combinatorial Optimization - Polyhedra and Efficiency" by Alexander Schrijver.

   (Not a beginner's book, but it has anything you ever wanted to know about P and NP.)

   thread
4. eruJun 2024
   Disclaimer: I have no clue of a complete learning path. But here are some suggestions you might find interesting.

   If you want to go heavy on complexity, you could try 'Combinatorial Optimization: Polyhedra and Efficiency' by Alexander Schrijver. But it's basically the equivalent of Knuth's Art of Computer Programming for complexity (in terms of rigour and breadth of approach).

   I have the three volumes of Schrijver's book on my desk, and even occasionally look into them. But I admit I never read the whole thing. I love the historical context he gives, eg explaining how maximum flow / minimum cut problems were first formally investigated in the Cold War when Western boffins wanted to work out how to most efficiently cut the Soviet rail network's ability to move stuff to Western Europe.

   If you want something much lighter, you could check out some of Scott Aaronson's backlog. Eg https://www.scottaaronson.com/papers/philos.pdf 'Why Philosophers Should Care About Computational Complexity'. You can follow his bibliography for more background. Scott's blog backlog is also good.

   If you like randomised algorithms, you might also like 'The Discrepancy Method Randomness and Complexity' by Bernard Chazelle. It's available for free online. Eg at https://api.pageplace.de/preview/DT0400.9781316047804_A25932...

   Apropos Bernard Chazelle, I'm working on a little paper myself. It's about how to simulate the outcome of a series of heap operations (like insert and delete-minimum) in O(n) time, instead of the trivial to achieve O(n log n) you get from a naive implementation. I'm looking for some collaborators, if you are interested.

   Show morethread
5. pcboumanJul 2021
   Mathematical Optimization still has many subfields that can be of interest. I guess that non-linear mathematical optimization is most more typical for many machine learning applications. Many pratical applications in scheduling, logistics, planning etc used linear (integer) programming and combinatorial optimization. The following are some points towards that body of literature.

   Alexander Schrijver [1] has lecture notes on Combinatorial Optimization on his website [2]. He also has an affordable 1800 page three volume set of books "Combinatorial Optimization - Polyhedra and Efficiency" [3], although I would say it is better suited as reference material because it is quite densely written.

   There is also the classic book "Combinatorial Optimization - Algorithms and Complexity" [4] by Papadimitriou (Bill Gates' MSc thesis supervisor) and Steiglitz that is a nice introduction to the topic as well.

   "In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation" by William J. Cook [5] is a more popular science book on the history of the Traveling Salesman Problem, that also explains how linear programming is used in the state of the art solvers, but is of course focuses on a very specific problem. There is also a book that contains all the scientific and mathematical details by Applegate, Bixby, Chvátal and Cook [6] if that is preferred.

   In recent years, there is a trend that mathematical optimization researchers work more with ML. In particular Dimitris Bertsimas has done some work on the intersection of those area's in recent years [7] and apparently has a book on the topic as well [8] (but I am not familiar with it).

   [1] https://homepages.cwi.nl/~lex/ [2] https://homepages.cwi.nl/~lex/files/dict.pdf [3] https://www.springer.com/us/book/9783540443896 [4] https://www.amazon.com/Combinatorial-Optimization-Algorithms... [5] https://press.princeton.edu/books/paperback/9780691163529/in... [6] http://www.math.uwaterloo.ca/tsp/book/index.html [7] https://dbertsim.mit.edu/papers/ [8] https://www.dynamic-ideas.com/books/machine-learning-under-a...

   Show morethread