Some aspects of studying an optimization or decision problem in different computational models
From MaRDI portal
Publication:1848391
DOI10.1016/S0377-2217(02)00269-2zbMath1058.90081OpenAlexW2153485748MaRDI QIDQ1848391
Gerhard-Wilhelm Weber, Klaus Meer
Publication date: 20 November 2002
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00269-2
Complexity theorySaturationAlgebraic models of computationLinear and quadratic programmingStructure of complexity classes
Abstract computational complexity for mathematical programming problems (90C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Effective optimization with weighted automata on decomposable trees, Cooperative grey games and the grey Shapley value
Cites Work
- A new polynomial-time algorithm for linear programming
- Elimination of quantifiers in algebraic structures
- On the existence of generally convergent algorithms
- Complexity of linear programming
- A survey on real structural complexity theory
- Saturation and stability in the theory of computation over the reals
- On the complexity of quadratic programming in real number models of computation
- P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
- The real number model in numerical analysis
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Computational complexity and feasibility of data processing and interval computations
- On the complexity of linear programming under finite precision arithmetic
- Efficient incremental algorithms for the sparse resultant and the mixed volume
- A note on non-complete problems in \(NP_\mathbb{R}\)
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Complexity estimates depending on condition and round-off error
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- Some NP-complete problems in quadratic and nonlinear programming
- On the Structure of Polynomial Time Reducibility
- On the Structure of $\cal NP_\Bbb C$
- Accessible telephone directories
- Machines Over the Reals and Non-Uniformity
- On digital nondeterminism
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- On Quadratic Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
