Lower bounds on the worst-case complexity of some oracle algorithms
From MaRDI portal
Publication:1251896
DOI10.1016/0012-365X(78)90097-3zbMath0392.68036MaRDI QIDQ1251896
Publication date: 1978
Published in: Discrete Mathematics (Search for Journal in Brave)
Lower BoundsOptimization ProblemsFixed-Point Problems for Continuous FunctionsIndependence SystemsOracle AlgorithmsWorst-Case Complexity
Related Items
On complexity of maximizatin of submodular functions*, Gradient methods of maximization of convex functions on discrete structures, Local optimization on graphs, More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments, The unbiased black-box complexity of partition is polynomial, Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity, K-greedy algorithms for independence systems, Dividing and conquering the square
Cites Work
- Extensions of Lemke's algorithm for the linear complementarity problem
- A nonlinear lower bound on linear search tree programs for solving knapsack-problems
- A lower bound on the number of additions in monotone computations
- Proving simultaneous positivity of linear forms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- An Analysis of the Greedy Heuristic for Independence Systems
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- PREDICTABLY COMPUTABLE FUNCTIONALS AND DEFINITION BY RECURSION
- The Approximation of Fixed Points of a Continuous Mapping
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
