The primal-dual tag has no wiki summary.
4
votes
1answer
250 views
LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?
Given any Integer Linear Program (ILP) there are 2 ways to approximate it:
Write down ILP, convert to LP by relaxing the integer constraints and round the solution
Write down the ILP, convert to LP ...
7
votes
2answers
269 views
An intuitive/informal proof for LP Duality?
What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of ...
13
votes
1answer
273 views
Is it enough for linear program constraints to be satisfied in expectation?
In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
1
vote
1answer
202 views
Difference between weak duality and strong duality?
For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:
Weak duality:
If $\bar{x}$ ...
1
vote
1answer
294 views
Primal vs dual decomposition methods
I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
7
votes
0answers
312 views
Difference between Primal Dual Algorithm for Proper and Uncrossable Functions
Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions:
(1) super-modular functions
(2) proper functions
...
3
votes
1answer
133 views
Primal Dual model in the continuous domain
The continuous max flow problem is posed as follows :
sup $\int_\Omega p_s(x)dx$
subject to :
$|p(x)| \le C(x); \forall x \in \Omega $
$p_s(x) \le C_s(x); \forall x \in \Omega $
$p_t(x) \le ...
29
votes
1answer
735 views
Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers
I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" ...
2
votes
2answers
245 views
Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.
Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship ...
11
votes
2answers
851 views
Generalization of the Hungarian algorithm to general undirected graphs?
The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight bipartite matching problem in polynomial time and anticipated the later development of the important ...
4
votes
2answers
248 views
Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?
Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that ...
4
votes
2answers
326 views
Online learning: Perceptron updates
It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?
