This is just a reminder for those who see it that I will discuss Part III essays in my office D1.13 tomorrow, Tuesday, at 3.30pm.
Monday, 30 November 2015
Lecture 22
I appreciate with hindsight that there was a lot to take in this this lecture. The punchline was that for an optimal auction (maximizing the seller's expected revenue), the fact that we want a direct revelation mechanism forces:
\[ P_i(\theta_i) = \theta_iV_i(\theta_i)-\int_{\theta_i^*}^{\theta_i} V_i(w)dw\tag{1}
\]
where $P_i(\theta_i)$ is bidder $i$'s expected payment (and $V_i(\theta_i)$ is his probability of winning the item) given that his valuation for the item is $\theta_i$, and thus that
\[ \text{seller's expected revenue}=E\left[\sum_i\phi_i(\theta_i)g(\theta_i)v_i(\theta_1,\ldots,\theta_n)\right].
\] So the auctioneer should arrange that for every $\theta_1,\dotsc,\theta_n$, he maximizes $\sum_i\phi_i(\theta_i)g(\theta_i)v_i(\theta_1,\ldots,\theta_n)$. This simply means awarding the item to the bidder with the largest non-negative value of $g(\theta_i)$, and not awarding the item to anyone if no $g(\theta_i)$ is positive.
This becomes more interesting when agents are heterogeneous, so that $F_i$ differ. The anaysis alters only slightly, becoming
\[ \text{seller's expected revenue}=E\left[\sum_i\phi_i(\theta_i)g_i(\theta_i)v_i(\theta_1,\ldots,\theta_n)\right].
\] For example, if $n=2$ and $\theta_1,\theta_2$ are independent and distributed $U[0,1]$ and $U[0,2]$ then $g_1(\theta_1)=2\theta_1-1$ and $g_2(\theta_2)=2\theta_2-2$. So the optimal auction is one in which
(a) Bidder 1 wins the item if $2\theta_1-1\geq 2\theta_2-2$ and $\theta_1\geq 1/2$.
(b) Bidder 2 wins the item if $2\theta_2-2> 2\theta_1-1$ and $\theta_2\geq 1$.
(c) Otherwise the item is not won.
\[ P_i(\theta_i) = \theta_iV_i(\theta_i)-\int_{\theta_i^*}^{\theta_i} V_i(w)dw\tag{1}
\]
where $P_i(\theta_i)$ is bidder $i$'s expected payment (and $V_i(\theta_i)$ is his probability of winning the item) given that his valuation for the item is $\theta_i$, and thus that
\[ \text{seller's expected revenue}=E\left[\sum_i\phi_i(\theta_i)g(\theta_i)v_i(\theta_1,\ldots,\theta_n)\right].
\] So the auctioneer should arrange that for every $\theta_1,\dotsc,\theta_n$, he maximizes $\sum_i\phi_i(\theta_i)g(\theta_i)v_i(\theta_1,\ldots,\theta_n)$. This simply means awarding the item to the bidder with the largest non-negative value of $g(\theta_i)$, and not awarding the item to anyone if no $g(\theta_i)$ is positive.
This becomes more interesting when agents are heterogeneous, so that $F_i$ differ. The anaysis alters only slightly, becoming
\[ \text{seller's expected revenue}=E\left[\sum_i\phi_i(\theta_i)g_i(\theta_i)v_i(\theta_1,\ldots,\theta_n)\right].
\] For example, if $n=2$ and $\theta_1,\theta_2$ are independent and distributed $U[0,1]$ and $U[0,2]$ then $g_1(\theta_1)=2\theta_1-1$ and $g_2(\theta_2)=2\theta_2-2$. So the optimal auction is one in which
(a) Bidder 1 wins the item if $2\theta_1-1\geq 2\theta_2-2$ and $\theta_1\geq 1/2$.
(b) Bidder 2 wins the item if $2\theta_2-2> 2\theta_1-1$ and $\theta_2\geq 1$.
(c) Otherwise the item is not won.
Appropriate payments for the auction design have to be worked out using (1). However, another way to figure the payments is by the VCG mechanism. This boils down to agent $i$ paying, when he wins, the least $\theta_i$ for which he would still win. E.g. in case (a) bidder 1 should win, and pay $\max\{\theta_2-1/2,1/2\}$.
Friday, 27 November 2015
Lecture 21
I mentioned
The ultimate prize for a Game of Thrones fan: the chance to become one of the many, many characters killed off by George RR Martin in the books that are inspiring the TV series. And now two fans have paid $20,000 each in an online charity auction to receive the honour of a character being named after them in the next novel – and seeing them "certainly meet a grisly death". (from the Guardian 12/06/14)
and for the sale of the Roman empire by auction, see: An Early Example of the “Wmner's Curse” in an Auction.
The ultimate prize for a Game of Thrones fan: the chance to become one of the many, many characters killed off by George RR Martin in the books that are inspiring the TV series. And now two fans have paid $20,000 each in an online charity auction to receive the honour of a character being named after them in the next novel – and seeing them "certainly meet a grisly death". (from the Guardian 12/06/14)
and for the sale of the Roman empire by auction, see: An Early Example of the “Wmner's Curse” in an Auction.
Wednesday, 25 November 2015
Lecture 20
I have thought that existing proofs of the Gibbert-Satterthwaite theorem are necessarily complicated and hard to explain. I was delighted to find a recent paper Yet Another Very Short Proof of the Gibbard-Satterthwaite Theorem, by Ville Korpela, October 2015, which I have adapted to provide the proof in section 20.3 and which I presented in today's lecture. I have added to pages 96-98 of the notes the proof that was given to students last year. You can compare and see which you think is easier to understand.
I did not prove Arrow's impossibility theorem. You can see at the link that its proof is quite long-winded.
It may at first seem a bit strange in 20.1 to call $f$ a social welfare function. Perhaps "social preference function" sounds more natural. However, in general, a social welfare function is a function which allows us to compare any two alternatives and say which is better, or that the are equal. In other contexts this can be done because the social welfare function associates to alternative $a$ a real number, say $f(a)$, and then alternative $a$ is preferred to $b$ iff $f(a)>f(b)$. Arrow's set up is more general,because $f$ outputs a linear order on the set of alternatives, $A$. So $a$ is preferred to $b$ iff $a\succ b$, where $\succ=f(\succ_1,\dotsc,\succ_n)$.
I have pretty much finished writing the lecture notes up to the end of the course, Lecture 23. The notes now include a table of contents and index. Since this year I have made a new reworking of the material I would appreciate hearing from you about any typos that you find in the notes, or things which you think could be better explained, while maintaining conciseness. I am deleting this year the topic of stable matchings which was originally listed in the draft schedules.
I did not prove Arrow's impossibility theorem. You can see at the link that its proof is quite long-winded.
It may at first seem a bit strange in 20.1 to call $f$ a social welfare function. Perhaps "social preference function" sounds more natural. However, in general, a social welfare function is a function which allows us to compare any two alternatives and say which is better, or that the are equal. In other contexts this can be done because the social welfare function associates to alternative $a$ a real number, say $f(a)$, and then alternative $a$ is preferred to $b$ iff $f(a)>f(b)$. Arrow's set up is more general,because $f$ outputs a linear order on the set of alternatives, $A$. So $a$ is preferred to $b$ iff $a\succ b$, where $\succ=f(\succ_1,\dotsc,\succ_n)$.
I have pretty much finished writing the lecture notes up to the end of the course, Lecture 23. The notes now include a table of contents and index. Since this year I have made a new reworking of the material I would appreciate hearing from you about any typos that you find in the notes, or things which you think could be better explained, while maintaining conciseness. I am deleting this year the topic of stable matchings which was originally listed in the draft schedules.
Monday, 23 November 2015
Lecture 19
I had worried that my proof of Theorem 18.2 was not sufficient. (I have not taken this from any textbook, but made it up.) On reflection, I think that it is. Do you agree? It is not the shortest proof of this result since it relies on first understanding the algorithm for finding a nucleolus on page 85. However, since we have that algorithm, we may as well use it. Notice that this algorithm does two things: it proves the nucleolus exists, and it shows that the nucleolus is unique. Another way to show the nucleolus exists is by appealing to compactness of the set in which we are looking for the lexicographic minimum.
I should have mentioned that the set of imputations might be empty. However, it is non-empty if the game is superadditive. There is a simple $x$ that will work as an imputation. Can you guess it? I will make this a question for Examples sheet 3. Notice that in (P1) on page 85 there is no requirement that $x$ be an imputation, only that it be efficient, in the sense that $\sum_{i\in N} x_i = v(N)$.
There are some very nice notes and slides for 12 lectures on cooperative games, by Stéphane Airiau. His notes for lectures 4 and 5 are particularly relevant to what I have presented about bargaining games, core and nucleolus. You might enjoy browsing the slides for a second view and to see more examples.
I should have mentioned that the set of imputations might be empty. However, it is non-empty if the game is superadditive. There is a simple $x$ that will work as an imputation. Can you guess it? I will make this a question for Examples sheet 3. Notice that in (P1) on page 85 there is no requirement that $x$ be an imputation, only that it be efficient, in the sense that $\sum_{i\in N} x_i = v(N)$.
There are some very nice notes and slides for 12 lectures on cooperative games, by Stéphane Airiau. His notes for lectures 4 and 5 are particularly relevant to what I have presented about bargaining games, core and nucleolus. You might enjoy browsing the slides for a second view and to see more examples.
Friday, 20 November 2015
Lecture 18
The slides used in today's lecture are: The disputed garment problem: the mathematics of bargaining and arbitration. (It is best to view this by downloading the file and then viewing with an app like Adobe Acrobat, so that you can see the slide transitioning.)
Wednesday, 18 November 2015
Lecture 17
It was a pity my coloured figure to explain Sperner's lemma in $\mathbb{R}^2$ did not show up well on the overhead projector. On page 82 of the notes I have now put a version with colours black, white and grey. I hope you can understand the lemma and its proof when you review this. You should see that the proof of the Brouwer fixed point theorem (via Sperner's lemma) and the Lemke-Howson algorithm use a common idea that a graph in which all vertices have degree 1 or 2 must have an even number of vertices of degree 1, and that given one vertex of degree 1 it is possible to find another by following a unique path.
Along
each side of the large triangle there is an odd number of edges whose two endpoints are
differently coloured. Entering along the base across such an
edge and following a path crossing edges which are similarly
coloured, we must, with at least one choice of initial entry
edge, reach a rainbow triangle. Notice that this also proves
that the number of rainbow triangles is odd. In this example
there are 3 rainbow triangles. Only one is found by
a following a path entering at the base. What happens in the above if you try to enter along an edge on the long right side whose endpoints are red and blue?
Notice that a linear programming problem can be formulated as linear complementarity problem and solved using Lemke's algorithm. (Quadratic programming with $D=0$.)
I have made some corrections and improvements at the bottom of page 80 of the notes. Here $w,z$ needed to be swapped, and I have tried to improve the explanation.
The formulation of a knapsack problem as a linear complementarity problem in 17.3 I took from the paper On the solution of NP-hard linear complementarity problems by Judice, Faustino and Martins Ribeiro, 2002. The authors conclude that Lemke's algorithm is not a good way to solve this LCP.
Notice that a linear programming problem can be formulated as linear complementarity problem and solved using Lemke's algorithm. (Quadratic programming with $D=0$.)
I have made some corrections and improvements at the bottom of page 80 of the notes. Here $w,z$ needed to be swapped, and I have tried to improve the explanation.
The formulation of a knapsack problem as a linear complementarity problem in 17.3 I took from the paper On the solution of NP-hard linear complementarity problems by Judice, Faustino and Martins Ribeiro, 2002. The authors conclude that Lemke's algorithm is not a good way to solve this LCP.
Monday, 16 November 2015
Lecture 16
Consider the decision problem: "Given a two-player game, does there exist a Nash equilibrium?" It is in NP, since given as a certificate a candidate equilibrium we can check that the answer is yes in polynomial time. But we don't actually need to do this, since by Nash's theorem the answer is always yes!
It is therefore more helpful to rephrase the question as a search problem: NASH: "Given a two-player game, either find a Nash equilibrium or output "no" if none exists." This problem can be solved in polynomial time by a nondeterministic Turing machine by examining all possible supports for the equilibrium strategies, so it is a problem in NP. It is not known whether or not NASH is NP-complete. However, many other problems are NP-complete, such as 2NASH: "Given a game and a Nash equilibrium, find another one, or output “no” if none exist."
Notice that the Lemke-Howson algorithm described today is not a polynomial time algorithm. Just as the the Klee-Minty example for the simplex algorithm, there are examples in which the length of the Lemke-Howson path grows exponentially in the size of the game. I will say more about the algorithm in the next lecture.
There is a good lecture by Papadimitriou on the question of: Complexity of Finding a Nash Equilibrium. He defines PPAD as the class of all search problems which always have a solution and whose proof is based on the parity argument for directed graphs. This includes the problem of finding a Nash equilibrium, where the proof is based on the Lemke-Howson algorithm. In fact, the other proof, based on the Brouwer fixed-point theorem, is also in this class, since a proof of the Brouwer fixed-point theorem uses Sperner's lemma, which is itself based on a parity argument in a directed graph.
It is therefore more helpful to rephrase the question as a search problem: NASH: "Given a two-player game, either find a Nash equilibrium or output "no" if none exists." This problem can be solved in polynomial time by a nondeterministic Turing machine by examining all possible supports for the equilibrium strategies, so it is a problem in NP. It is not known whether or not NASH is NP-complete. However, many other problems are NP-complete, such as 2NASH: "Given a game and a Nash equilibrium, find another one, or output “no” if none exist."
Notice that the Lemke-Howson algorithm described today is not a polynomial time algorithm. Just as the the Klee-Minty example for the simplex algorithm, there are examples in which the length of the Lemke-Howson path grows exponentially in the size of the game. I will say more about the algorithm in the next lecture.
There is a good lecture by Papadimitriou on the question of: Complexity of Finding a Nash Equilibrium. He defines PPAD as the class of all search problems which always have a solution and whose proof is based on the parity argument for directed graphs. This includes the problem of finding a Nash equilibrium, where the proof is based on the Lemke-Howson algorithm. In fact, the other proof, based on the Brouwer fixed-point theorem, is also in this class, since a proof of the Brouwer fixed-point theorem uses Sperner's lemma, which is itself based on a parity argument in a directed graph.
Saturday, 14 November 2015
Lecture 15
The normal form games studied today are one in which both players take actions simultaneously. A sequential game, like chess, can in principle be made into a normal form game, but each pure strategy for white would need to be a complete specification of the moves white would make in each possible board position that could be reached by prior moves of white and black playing in some way. The number of pure strategies for white would need to exceed the Shannon number, which is the number of different games of chess that can be played. It is thought to be about $10^{120}$.
Thursday, 12 November 2015
Wednesday, 11 November 2015
Lecture 14
The re-edited proof of the PTAS for knapsack that in now on page 59 of the notes looks to me to be correct. We need to say that when we fill up after $K$ using the greedy algorithm we use only items with values no more than values in $K$. This ensures that when $K=H$, where $H$ is the $m$ most valuable items in $O$, we find the bound $v(O)\leq v(H\cup G)+v_j$ and we can be sure that $v_j\leq v(H)/m\leq v(O)/m$.
In the Euclidean case of the travelling salesman problem distances are symmetric and satisfy a metric (i.e. triangle inequality). This restriction of the problem is in APX (while the general problem is not). It is easy to find a 2-approximation algorithm in the Euclidean case (a question on Examples sheet 2.) This can be improved to a 3/2-approximation algorithm due to Christofides in 1976. An even better approximation algorithm was found in 2011. It is a 1.4999999999999999999999999999999999999999999999999996-approximation algorithm (compared to Christofides's 1.5). See Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem.
An excellent web site with history of the TSP and many facts about it is The Traveling Salesman Problem at the University of Waterloo.
There is a very nice demo of simulated annealing applied to the travelling salesman problem by Schneider, The Traveling Salesman with Simulated Annealing, R, and Shiny. I showed this in today's lecture.
A Mathematica program running Nearest neighbour, 2OPT and Simulated annealing is here.
It is common to speak of simulated annealing as being a meta-heuristic, because it is readily applicable to a large variety of problems. Other meta-heuristics are genetic algorithms, ant colony optimization and particle swarm optimization. (Many heuristics try to draw on something that nature appears to do well.)
In the Euclidean case of the travelling salesman problem distances are symmetric and satisfy a metric (i.e. triangle inequality). This restriction of the problem is in APX (while the general problem is not). It is easy to find a 2-approximation algorithm in the Euclidean case (a question on Examples sheet 2.) This can be improved to a 3/2-approximation algorithm due to Christofides in 1976. An even better approximation algorithm was found in 2011. It is a 1.4999999999999999999999999999999999999999999999999996-approximation algorithm (compared to Christofides's 1.5). See Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem.
An excellent web site with history of the TSP and many facts about it is The Traveling Salesman Problem at the University of Waterloo.
There is a very nice demo of simulated annealing applied to the travelling salesman problem by Schneider, The Traveling Salesman with Simulated Annealing, R, and Shiny. I showed this in today's lecture.
A Mathematica program running Nearest neighbour, 2OPT and Simulated annealing is here.
It is common to speak of simulated annealing as being a meta-heuristic, because it is readily applicable to a large variety of problems. Other meta-heuristics are genetic algorithms, ant colony optimization and particle swarm optimization. (Many heuristics try to draw on something that nature appears to do well.)
Monday, 9 November 2015
Lecture 13
I have rewritten Section 13.1 of the notes (arguments for a PTAS for the knapsack problem.) I will discuss this in the next lecture. I have also added notes for Lectures 14 and 15 (which may be subject to small revisions.)
As some of us talked of after the lecture, the branch and bound algorithm can be generalised to the alpha-beta pruning algorithm, which lies at the heart of programs that play strategic board games like chess and reversi.
When looking for a branch and bound tool I might show you (see next paragraph), I came across an article, Branch And Bound—Why Does It Work?, in which the author addresses the question of why it is difficult to prove a concrete result about average running time of the branch and bound algorithm. I once spent some time trying to investigate this question myself, without any success. The author makes the provocative comment that doing something on this problem rings bells in ones mind with the famous Collatz conjecture.
I showed you briefly this nice interactive branch and bound solver for the knapsack problem, by Jacopo Corbetta, which can help you to understand the algorithm. I suggest pressing "add item" until you have 7 items, and then put max weight = 20. Click on "start solving" and then choose where to "branch", successively, until you find the optimal solution. Here is the start of the tree. Notice that branches of increasing depth are indicated by indentation to the right.
As some of us talked of after the lecture, the branch and bound algorithm can be generalised to the alpha-beta pruning algorithm, which lies at the heart of programs that play strategic board games like chess and reversi.
When looking for a branch and bound tool I might show you (see next paragraph), I came across an article, Branch And Bound—Why Does It Work?, in which the author addresses the question of why it is difficult to prove a concrete result about average running time of the branch and bound algorithm. I once spent some time trying to investigate this question myself, without any success. The author makes the provocative comment that doing something on this problem rings bells in ones mind with the famous Collatz conjecture.
I showed you briefly this nice interactive branch and bound solver for the knapsack problem, by Jacopo Corbetta, which can help you to understand the algorithm. I suggest pressing "add item" until you have 7 items, and then put max weight = 20. Click on "start solving" and then choose where to "branch", successively, until you find the optimal solution. Here is the start of the tree. Notice that branches of increasing depth are indicated by indentation to the right.
Solution
Current best value: zcur = (none)
Possible branches: 3
Step 1a Branch constraints: x6=0
Optimal value for the relaxed problem: 25.714285714285715 (remaining weight: 0)
x: 1111100.7142857142857143
Optimal value for the relaxed problem: 25.714285714285715 (remaining weight: 0)
Step 0 Branch constraints: (none)
Optimal value for the relaxed problem: 25.833333333333336 (remaining weight: 0)
x: 111110.83333333333333340
Optimal value for the relaxed problem: 25.833333333333336 (remaining weight: 0)
x: 111110.83333333333333340
Step 2a Branch constraints: x5=0 x6=1
Optimal value for the relaxed problem: 25.57142857142857 (remaining weight: 0)
x: 1111010.5714285714285714
Optimal value for the relaxed problem: 25.57142857142857 (remaining weight: 0)
x: 1111010.5714285714285714
Step 1b Branch constraints: x6=1
Optimal value for the relaxed problem: 25.8 (remaining weight: 0)
x: 11110.810
Optimal value for the relaxed problem: 25.8 (remaining weight: 0)
x: 11110.810
Step 2b Branch constraints: x5=1 x6=1
Optimal value for the relaxed problem: 25.75 (remaining weight: 0)
x: 1110.75110
Optimal value for the relaxed problem: 25.75 (remaining weight: 0)
x: 1110.75110
Friday, 6 November 2015
A Big Result On Graph Isomorphism
A very interesting thing was mentioned in the BBC radio programme: namely that on 4 November, 2015 László Babai announced a new result for the graph isomorphism problem. You may recall that this problem is conjectured to be NP-intermediate, being neither in P or NP-complete. The new result is that there is an quasi-polynomial time algorithm for this problem. This shows that the problem is much closer to being in P than to being NP-complete. See A Big Result On Graph Isomorphism.
P vs NP on Radio 4
Yesterday morning the subject of P vs NP was discussed on BBC Radio 4's In Our Time.
"Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. ..."
You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.
"Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. ..."
You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.
Lecture 12
The slides I used today to talk about the rendezvous problem are linked here. The paper is
R. R. Weber, Optimal symmetric rendezvous search on three locations, Math Oper Res., 37(1): 111-122, 2012.
It was in solving this problem that I first came to study semidefinite programming. I am fond of this paper because of the way it employs a range of mathematical tools on the way to proving the main theorem. Indeed, I today discovered that there is an AMS review of this paper which says, "The author dedicates many pages to the proof of the theorem, utilizing multiple ideas from probability theory, game theory, linear algebra, linear programming, and semidefinite programming."
I mentioned today the class APX, consisting of optimization problems that are approximable, in the sense that there exists a polynomial time algorithm which can always find an answer that is within a fixed multiplicative factor of the optimal answer. One example of an APX problem is the travelling salesman problem with distances satisfying the triangle inequality. For this problem there exists a 2-approximation algorithm based on the efficient solution of the minimum spanning tree problem. (This will be a question for you on Examples sheet 2.) This problem is also APX-complete, in that it is as hard as any other in problem in APX.
Another APX-complete problem is minimum vertex cover. This also has a 2-approximation algorithm: just find a maximum matching and then include in the vertex cover both endpoints of the edges in the matching. Do you see why this works?
We now know about P, NP, NP-hard, NP-complete and APX. There is a huge "zoo" of complexity classes. The entertaining complexity zoo web site lists 498 complexity classes that have been defined by researchers.
R. R. Weber, Optimal symmetric rendezvous search on three locations, Math Oper Res., 37(1): 111-122, 2012.
It was in solving this problem that I first came to study semidefinite programming. I am fond of this paper because of the way it employs a range of mathematical tools on the way to proving the main theorem. Indeed, I today discovered that there is an AMS review of this paper which says, "The author dedicates many pages to the proof of the theorem, utilizing multiple ideas from probability theory, game theory, linear algebra, linear programming, and semidefinite programming."
I mentioned today the class APX, consisting of optimization problems that are approximable, in the sense that there exists a polynomial time algorithm which can always find an answer that is within a fixed multiplicative factor of the optimal answer. One example of an APX problem is the travelling salesman problem with distances satisfying the triangle inequality. For this problem there exists a 2-approximation algorithm based on the efficient solution of the minimum spanning tree problem. (This will be a question for you on Examples sheet 2.) This problem is also APX-complete, in that it is as hard as any other in problem in APX.
Another APX-complete problem is minimum vertex cover. This also has a 2-approximation algorithm: just find a maximum matching and then include in the vertex cover both endpoints of the edges in the matching. Do you see why this works?
We now know about P, NP, NP-hard, NP-complete and APX. There is a huge "zoo" of complexity classes. The entertaining complexity zoo web site lists 498 complexity classes that have been defined by researchers.
Wednesday, 4 November 2015
Wikipedia articles
In these blog entries, I often provide links to Wikipedia articles. In my experience, Wikipedia articles tend to be rather good in the fields of computer science and operations research. They have been refined by experts and often give introductions to topics that are illuminating while remaining concise. I particularly like what these articles contain about the history of methods. For example, who was Dijkstra, for whom Dijkstra's algorithm is named? (One might guess from the name that he must be a Ducthman!)
One needs to be critical, but errors tend to be few since many eagle-eyed persons have poured over the articles. For example, the articles on Max-flow min-cut theorem and Konig's theorem are interesting to read in conjunction with Lecture 10.
One needs to be critical, but errors tend to be few since many eagle-eyed persons have poured over the articles. For example, the articles on Max-flow min-cut theorem and Konig's theorem are interesting to read in conjunction with Lecture 10.
Lecture 11
At the start of today's lecture I explained the Hungarian algorithm, which is a polynomial time algorithm for solving the assignment problem. My emphasis was on explaining why it works. In practice the algorithm looks rather different. The fact that one is adjusting node numbers and solving maximum matching problems is rather hidden from view.
You might like to read this nice tutorial on the Hungarian algorithm and read through the simple Example 2 on pages 18-27.
The algorithms in Lecture 11 are all polynomial time algorithms: Bellman-Ford, Dijkstra's and Prim's algorithms. They do involve numbers $c_{ij}$, but the the calculations that must be done with these numbers, such as adding (to find $c_{ij}+\lambda_j$) and comparing (to find $\min\{c_{it},c_{ij}+c_{jt}\}$) can all be done in time that is polynomial in the size of the input, as measured in numbers of binary bits. This is why running time is depends most crucially on the number of vertices $|V|$ and number of edges $|E|$.
One should be aware that for graphs with special structure, perhaps very sparse in edges, there exist specially tailored versions of some of our algorithms, which have better running time than those quoted in this lecture for a complete graph where $|E|=|V|^2$.
You might like to read this nice tutorial on the Hungarian algorithm and read through the simple Example 2 on pages 18-27.
The algorithms in Lecture 11 are all polynomial time algorithms: Bellman-Ford, Dijkstra's and Prim's algorithms. They do involve numbers $c_{ij}$, but the the calculations that must be done with these numbers, such as adding (to find $c_{ij}+\lambda_j$) and comparing (to find $\min\{c_{it},c_{ij}+c_{jt}\}$) can all be done in time that is polynomial in the size of the input, as measured in numbers of binary bits. This is why running time is depends most crucially on the number of vertices $|V|$ and number of edges $|E|$.
One should be aware that for graphs with special structure, perhaps very sparse in edges, there exist specially tailored versions of some of our algorithms, which have better running time than those quoted in this lecture for a complete graph where $|E|=|V|^2$.
Tuesday, 3 November 2015
Examples sheet 1 #4
There was some question in the class about a part of the argument. Consider
\begin{align}
\max\;\{\; & 0^T x:\,Ax=b,\, x\geq 0\;\} \tag{1} \\
\min\;\{\; & y^T b:\, y^T A\geq 0^T\;\} \tag{2}
\end{align}
If (1) is feasible then for feasible $x,y$ we have $y^T b= (y^T A) x\geq 0$, so (2) is bounded.
On the other hand, if (2) is bounded then it is feasible and bounded. The strong duality theorem for linear programming states that (1) is feasible and bounded if and only if (2) is feasible and bounded. So (1) is feasible. This is enough to answer the question.
But how do we prove strong duality for linear programming? One way to prove it is via Farkas Lemma, which in the context of this question would be cheating. Another way is by appeal to the supporting hyperplane theorem and the sufficient conditions (satisfied by linear programs) for $\phi(b)$ to be convex.
I now think (c) of this question would be better phrased as "The Strong Duality theorem for linear programming states that if a linear programming problem is both feasible and bounded, then so is its dual." Show that this implies Farkas Lemma."
Monday, 2 November 2015
Lecture 10
I have been working on the notes for this lecture and have now added several further figures. Please make sure you have an up-to-date copy of the notes, as there were some errors in previous versions.
I will talk about the Hungarian algorithm for the assignment problem at the start of next lecture.
I mentioned that in a problem where all edge capacities are integers the Ford-Fulkerson algorithm runs in time $O(|E|\cdot f)$, where $f$ is some bound on the total flow. If edge capacities are not integers, one can still apply the Ford-Fulkerson algorithm, but it is not guaranteed to converge. There are examples in which one can increase flows on augmenting paths by ever smaller and smaller amounts, but not even converge to the optimal flow.
To understand the proofs of Hall's marriage theorem and Konig's theorem, you really need to sit down and carefully study for yourself an example, as I have now provided in Figure 12.
There are many nice applications in which the min-cut max-flow theorem can be used to obtain other results, by applying it to the right network. Another example of this is Menger's theorem: Let $G$ be a finite undirected graph and $x$ and $y$ two distinct vertices. Then the minimum number of edges whose removal disconnects $x$ and $y$ is equal to the maximum number of pairwise edge-independent paths from $x$ to $y$. This theorem is proved similarly to Konig's theorem.
I will talk about the Hungarian algorithm for the assignment problem at the start of next lecture.
I mentioned that in a problem where all edge capacities are integers the Ford-Fulkerson algorithm runs in time $O(|E|\cdot f)$, where $f$ is some bound on the total flow. If edge capacities are not integers, one can still apply the Ford-Fulkerson algorithm, but it is not guaranteed to converge. There are examples in which one can increase flows on augmenting paths by ever smaller and smaller amounts, but not even converge to the optimal flow.
To understand the proofs of Hall's marriage theorem and Konig's theorem, you really need to sit down and carefully study for yourself an example, as I have now provided in Figure 12.
There are many nice applications in which the min-cut max-flow theorem can be used to obtain other results, by applying it to the right network. Another example of this is Menger's theorem: Let $G$ be a finite undirected graph and $x$ and $y$ two distinct vertices. Then the minimum number of edges whose removal disconnects $x$ and $y$ is equal to the maximum number of pairwise edge-independent paths from $x$ to $y$. This theorem is proved similarly to Konig's theorem.
Subscribe to:
Posts (Atom)