𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Local Approximability of Max-Min and Min-Max Linear Programs

✍ Scribed by Patrik Floréen; Marja Hassinen; Joel Kaasinen; Petteri Kaski; Topi Musto; Jukka Suomela

Publisher
Springer
Year
2010
Tongue
English
Weight
823 KB
Volume
49
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Linear max-min programming
Linear max-min programming
✍ Marc E. Posner; Chu-Tao Wu 📂 Article 📅 1981 🏛 Springer-Verlag 🌐 English ⚖ 321 KB
Solving min-max problems and linear semi
Solving min-max problems and linear semi-infinite programs
✍ S.-C. Fang; Soon-Yi Wu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 309 KB

For a min-max problem in the form of minxEx maxtET {A(X)}, the nondi\_fferentiability of the max function F(x) --maxtET {ft(x)} presents special difficulty in finding optimal solutions. We show that an entropic regularization procedure can provide a smooth approximation Fp(x) that uniformly converge

Complexity of the min–max and min–max re
Complexity of the min–max and min–max regret assignment problems
✍ Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 179 KB

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment pro

Approximation hardness of min–max tree c
Approximation hardness of min–max tree covers
✍ Zhou Xu; Qi Wen 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 367 KB

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees.