Complexity aspects of a semi-infinite optimization problemFootnote†

†Dedicated to H.Th. Jongen on the occasion of his 60th birthday

References

• Blum , L , Shub , M and Smale , S . 1989 . Bull. Amer. Mathe. Soci . On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines , 21 : 1 – 46 .
   Google Scholar
• Blum , L , Cucker , F , Shub , M and Smale , S . 1998 . Complexity and Real Computation , New York : Springer .
   Google Scholar
• Cucker , F and Matamala , M . 1996 . Math. Syst. Theory . On digital nondeterminism , 29 : 635 – 647 .
   Google Scholar
• Cucker , F , Shub , M and Smale , S . 1994 . Theor. Comput. Sci . Complexity separations in Koiran's weak model , 133 : 3 – 14 .
   Google Scholar
• Garey , MR and Johnson , DS . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness , San Francisco : W.H. Freeman .
   Google Scholar
• Gelfand , IM , Kapranov , MM and Zelevinsky , AV . 1994 . Discriminants, Resultants, and Multidimensional Determimants , Boston : Birkhäuser .
   Google Scholar
• ÅGustafson , S and Kortanek , KO . 1983 . Semi-infinte programming and applications, in Mathematical Programming: The State of the Art , Edited by: Bachem , A , Grötschel , M and Korte , B . 132 – 157 . New York : Springer .
   Google Scholar
• Hettich , R and Th. Jongen , H . 1978 . “ Part 2, Lecture Notes in Control and Inform. Sci., 7 ” . In Semi-infinite Programming: conditions of optimality and applications, Optimization Techniques , Edited by: Stoer , J . 1 – 11 . New York : Springer .
   Google Scholar
• Hettich , R and Kortanek , KO . 1993 . SIAM Rev . Semi-infinite Programming , 35 : 380 – 429 .
   Google Scholar
• Th.Jongen , H , Meer , K and Triesch , E . 2004 . Optimization Theory , Kluwer : Dortrecht .
   Google Scholar
• Th. Jongen , H , Twilt , F and Weber , GW . 1992 . Semi-infinite optimization: structure and stability of the feasible set, J. Opt. Theory Appl. , 72 : 529 – 552 .
   Google Scholar
• Karmarkar , N . 1984 . Combinatorica . A new polynomial time algorithm for linear programming , 4 : 373 – 395 .
   Google Scholar
• Khachiyan , LG . 1979 . A polynomial algorithm in linear programming , Vol. 244 , 1093 – 1096 . Dokl : Akad. Nauk USSR . (English translation in: Soviet Math. Dokl. 20, pp. 191–194
   Google Scholar
• Koiran , P . 1993 . “ 34th Annual IEEE Symposium on Foundations of Compu. Sci. N/A ” . In A weak version of the Blum-Shub-Smale model 486 – 495 .
   Google Scholar
• Koshelev , M , Longpré , L and Taillibert , P . 1998 . Reliable Comput . Optimal enclusure of quadratic interval functions , 4 : 351 – 360 .
   Google Scholar
• Kreinovich , V , Lakeyev , AV , Rohn , J and Kahl , P . 1997 . Computational Complexity and Feasibility of Data Processing and Interval Computations , Dortrecht : Kluwer .
   Google Scholar
• Makowsky , J and Meer , K . 2002 . Polynomials of bounded tree-width Foundations of Computational Mathematics , Edited by: Cucker , F and Rojas , JM . 211 – 250 . New Jersey : World Scientific . Festschrift on the occasion of Steve Smale's 70th birthday
   Google Scholar
• Meer , K . 1994 . Theor. Comput. Sci . On the complexity of Quadratic Programming in real number models of computation , 133 : 85 – 94 .
   Google Scholar
• Meer , K . 2004 . Reliable Comput . On a refined analysis of some problems in interval arithmetic using real number complexity theory , 10 : 209 – 225 .
   Google Scholar
• Plaisted , DA . 1984 . Theor. Compu. Sci . New NP-hard and NP-complete polynomial and integer divisibility problems , 31 : 125 – 138 .
   Google Scholar
• Rohn , J . 1994 . Computing . Enclosing solutions of linear interval equations is NP-hard , 53 : 365 – 368 .
   Google Scholar
• Stockmeyer , L . 1977 . Theor. Comput. Sci . The polynomial-time hierarchy , 3 : 1 – 22 .
   Google Scholar
• Tichatschke , R , Hettich , R and Still , G . 1989 . ZOR–Methods Models Oper. Res . Connections between generalized inexact and semi-infinite linear programming , 33 : 367 – 382 .
   Google Scholar
• Traub , JF and Woźniakowski , H . 1982 . Oper. Res. Lett . Complexity of linear programming , 1 : 59 – 62 .
   Google Scholar