Computationally Inexpensive Algorithm

A Computationally Expensive Algorithm is an algorithm that requires a small number of steps to complete relative to its task input size.

• AKA: Efficient Algorithm.
• Context:
  • It can (typically) have a Low Computational Complexity.
  • …
• Example(s):
  • an Heuristic Algorithm,
  • PAMELI Algorithm (Cuervo et al., 2021),
  • SOCEMO Algorithm (Muller, 2017),
• Counter-Example(s):
  • Computationally Expensive Algorithm,
  • Memory Unintensive Algorithm.
• See: P Task, Computational Complexity Theory, Polynomial-time Algorithm, Constant-time Algorithm.

---

---

References

2021

• (Cuervo et al., 2021) ⇒ Santiago Cuervo, Miguel Melgarejo, Angie Blanco-Canon, Laura Reyes-Fajardo, and Sergio Rojas-Galeano (2021). "PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems". arXiv preprint arXiv:2103.10736.
  • QUOTE: We present an algorithm for multi-objective optimization of computationally expensive problems (...)

    We synthesize these ideas in our proposed algorithm for multi-objective optimization, called Pareto set Approximation by Meta-Exploration of Landscape Identifiers (PAMELI). The pseudocode of PAMELI is presented in Algorithm 1 and Fig. 2 illustrates its components and the relations between them.

2019

• (Chugh et al., 2019) ⇒ Tinkle Chugh, Karthik Sindhya, Jussi Hakanen, and Kaisa Miettinen (2019). "A Survey On Handling Computationally Expensive Multiobjective Optimization Problems with Evolutionary Algorithms". In: Soft Computing, 23(9), 3137-3166. DOI:10.1007/s00500-017-2965-0.
  • QUOTE: In many problems, explicit formulations of objective or constraint functions are not known and such functions are called black box functions. Usually, problems involving such functions need a long time to be solved e.g. problems involving computational fluid dynamics simulations utilizing finite element algorithms take substantial time to obtain one solution. These are examples of problems that we refer to as computationally expensive multiobjective optimization problems.

2009

• (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The status of the P versus NP problem.” In: Communications of the ACM, 52(9).
  • In 1965, Jack Edmonds12 gave an efficient algorithm to solve this matching problem and suggested a formal definition of “efficient computation” (runs in time a fixed polynomial of the input size). The class of problems with efficient solutions would later become known as P for "Polynomial Time."

---