Lower bounds on the worst-case complexity of some oracle algorithms

DOI10.1016/0012-365X(78)90097-3zbMath0392.68036MaRDI QIDQ1251896

Bernhard Korte, Dirk Hausmann

Publication date: 1978

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Lower BoundsOptimization ProblemsFixed-Point Problems for Continuous FunctionsIndependence SystemsOracle AlgorithmsWorst-Case Complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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