commit b2ff30ab2a62525e7771946f33d3496fe111bfc0
parent 016cde6b1bdb4fe382bd21c2a49e93b0d094c540
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 5 Mar 2025 15:35:00 +0100
commit with codex
Diffstat:
6 files changed, 29 insertions(+), 7 deletions(-)
diff --git a/approximation_class b/approximation_class
@@ -1,10 +1,10 @@
# Approximation classes
-- FPRAS [fpras]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure
+- [FPRAS]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure
- variant QPRAS [qpras] with "quasi-polynomial time" [quasipolynomial]
-- PRAS [pras]: same but not polynomial in 1/e
-- without R, a deterministic algorithm (PRAS vs PTAS [ptas], FPRAS vs FPTAS [fptas])
-- APX [apx]: there is an approximation algorithm for a certain fixed epsilon
+- [PRAS]: same but not polynomial in 1/e
+- without R, a deterministic algorithm (PRAS vs [PTAS], FPRAS vs [FPTAS])
+- [APX]: there is an [approximation_algorithm] for a certain fixed epsilon
Up: [complexity_class] of [approximation]
diff --git a/maximum_linear_arrangement b/maximum_linear_arrangement
@@ -0,0 +1,7 @@
+# Maximum linear arrangement
+
+cf [alemanypuig2024maximum]
+
+See also: [minimum_linear_arrangement]
+
+Up: [computational_problem] on [graph]
diff --git a/minimization b/minimization
@@ -5,3 +5,7 @@
- [automaton_minimal]
Up: [theoretical_computer_science]
+
+Aliases: minimized
+
+See also: [minimum], [maximization]
diff --git a/minimum b/minimum
@@ -7,6 +7,6 @@ The smallest element of an [order]
Up: [mathematics_basic_concepts]
-See also: [maximum]
+See also: [maximum], [minimization]
Aliases: min
diff --git a/minimum_linear_arrangement b/minimum_linear_arrangement
@@ -0,0 +1,11 @@
+# Minimum linear arrangement
+
+Given a [graph], find a [permutation] of the [vertices] such that the [sum] across [edges] of the difference between the permutation image of the two endpoint [vertices] is [minimized]
+
+The problem is [NP_complete]
+
+cf [bienkowski2024improved]
+
+Up: [computational_problem] on [graph]
+
+See also: [graph_layout], [maximum_linear_arrangement]
diff --git a/submodular_maximization b/submodular_maximization
@@ -1,8 +1,8 @@
# Submodular maximization
-[np_hard]
+An [NP_hard] [computational_problem]
-[buchbinder2024deterministic]
+cf [buchbinder2024deterministic]
Up: [submodular_optimization], [maximization]
