# Tagged Questions

The primal-dual tag has no wiki summary.

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 ...
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 ...
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 ...
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}$ ...
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 ...
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 ...
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 ...
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" ...
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 ...
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 ...
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 ...
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?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9106829166412354, "perplexity_flag": "middle"}