New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:27, 15 February 2023 Median (hist | edit) [1,236 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Median (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, determine the median $m$ of the graph, where $m := \min\limits_{v\in V} \sum\limits_{u\in V} d(u, v)$ == Related Problems == Related: Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, constant sensitivity (4/3)-approxi...")
- 10:27, 15 February 2023 Unbalanced OV (hist | edit) [1,257 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unbalanced OV (Orthogonal Vectors)}} == Description == Let $0 < \alpha \leq 1$. UOV is the OV problem with the specifications that $A$ is of size $n$ and $B$ is of size $m=\Theta(n^\alpha)$ and $d\leq n^{o(1)}$. == Related Problems == Generalizations: OV Related: k-OV, 3-OV == Parameters == <pre>$n$: size of $A$ $m$: size of $B$ $d$: dimensionality of vectors</pre> == Table of Algorithms == Currently no algorithms in our database fo...")
- 10:27, 15 February 2023 3-OV (hist | edit) [1,200 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-OV (Orthogonal Vectors)}} == Description == Given 3 sets of $d$-dimensional vectors $A_1, A_2, A_3$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, a_3 \in A_3$ such that $a_1 * a_2 * a_3 = 0$? == Related Problems == Generalizations: k-OV Related: OV, Unbalanced OV == Parameters == <pre>$n$: number of vectors per set $d$: dimension of each vector; $d = omega(log(n))$</pre> == Table of Algorithms == Currently no algo...")
- 10:27, 15 February 2023 K-OV (hist | edit) [2,102 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-OV (Orthogonal Vectors)}} == Description == Given $k$ sets of $d$-dimensional vectors $A_1, A_2, \ldots, A_k$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, \ldots, a_k \in A_k$ such that $a_1 * a_2 * \ldots * a_k = 0$? == Related Problems == Subproblem: OV, 3-OV Related: 3-OV, Unbalanced OV == Parameters == <pre>$n$: number of vectors per set $k$: number of sets $d$: dimension of each vector; $d = omega(log(n))$...")
- 10:27, 15 February 2023 OV (hist | edit) [5,802 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:OV (Orthogonal Vectors)}} == Description == Given $n$ vectors in $\{0,1\}^{O(\log n)}$, are two of them orthogonal? == Related Problems == Generalizations: k-OV Subproblem: Unbalanced OV Related: 3-OV == Parameters == <pre>$n$: number of vectors $d$: dimension of each vector; $d = O(log(n))$ typically</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Sp...")
- 10:27, 15 February 2023 MaxSAT (hist | edit) [2,980 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:MaxSAT (Boolean Satisfiability)}} == Description == Given an instance of SAT represented in Conjunctive Normal Form (CNF), compute an assignment to the variables that maximizes the number of satisfied clauses. == Related Problems == Generalizations: Conjunctive Normal Form SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE...")
- 10:27, 15 February 2023 Renamable Horn (hist | edit) [1,109 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Renamable Horn (Boolean Satisfiability)}} == Description == Renamable Horn asks the question whether or not there exists a subset of variables that can be negated such that the boolean formula is turned into a Horn formula == Related Problems == Generalizations: Horn SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT,...")
- 10:27, 15 February 2023 Dual-Horn SAT (hist | edit) [784 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dual-Horn SAT (Boolean Satisfiability)}} == Description == Dual-Horn SAT restricts the boolean formula to the conjunction of dual-Horn clauses, i.e. clauses with at most one negated literal == Related Problems == Generalizations: Horn SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, [[Not-All-Equal 3-SAT (NAE 3SAT)]...")
- 10:27, 15 February 2023 Horn SAT (hist | edit) [808 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Horn SAT (Boolean Satisfiability)}} == Description == Horn SAT restricts the boolean formula to the conjunction of Horn clauses, i.e. clauses with at most one positive literal == Related Problems == Generalizations: Conjunctive Normal Form SAT Subproblem: Dual-Horn SAT, Renamable Horn Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All...")
- 10:27, 15 February 2023 XOR-SAT (hist | edit) [695 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:XOR-SAT (Boolean Satisfiability)}} == Description == XOR-SAT replaces the ORs in CNF with XORs == Related Problems == Generalizations: Conjunctive Normal Form SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-SAT, 2SAT, 3SAT, 3SAT-5, 4SAT,...")
- 10:27, 15 February 2023 Monotone 3SAT (hist | edit) [772 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone 3SAT (Boolean Satisfiability)}} == Description == Monotone 3SAT is 3SAT with the restriction that all of the literals in a clause are either all negated or all positive == Related Problems == Generalizations: 3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone No...")
- 10:27, 15 February 2023 4SAT (hist | edit) [1,033 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4SAT (Boolean Satisfiability)}} == Description == 4SAT restricts the boolean formula to CNF with (at most) 4 literals per clause == Related Problems == Generalizations: k-SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), [[2SAT]...")
- 10:27, 15 February 2023 3SAT-5 (hist | edit) [736 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SAT-5 (Boolean Satisfiability)}} == Description == 3SAT-5 is 3SAT with the restriction that each variable occurs in at most 5 clauses == Related Problems == Generalizations: 3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), ...")
- 10:27, 15 February 2023 3SAT (hist | edit) [1,486 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SAT (Boolean Satisfiability)}} == Description == 3SAT restricts the boolean formula to CNF with (at most) 3 literals per clause == Related Problems == Generalizations: k-SAT Subproblem: 1-in-3SAT, Not-All-Equal 3-SAT (NAE 3SAT), 3SAT-5, Monotone 3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal...")
- 10:27, 15 February 2023 2SAT (hist | edit) [732 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2SAT (Boolean Satisfiability)}} == Description == 2SAT restricts the boolean formula to CNF with (at most) 2 literals per clause == Related Problems == Generalizations: k-SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), [[3SAT]...")
- 10:27, 15 February 2023 K-SAT (hist | edit) [1,694 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-SAT (Boolean Satisfiability)}} == Description == k-SAT restricts the boolean formula to CNF with (at most) k literals per clause == Related Problems == Generalizations: Conjunctive Normal Form SAT Subproblem: 2SAT, 3SAT, 4SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3...")
- 10:27, 15 February 2023 Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) (hist | edit) [780 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) (Boolean Satisfiability)}} == Description == Monotone NAE 3SAT is NAE 3SAT with the restriction that all of the literals in a clause are either all negated or all positive == Related Problems == Generalizations: Not-All-Equal 3-SAT (NAE 3SAT) Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT,...")
- 10:27, 15 February 2023 Not-All-Equal 3-SAT (NAE 3SAT) (hist | edit) [876 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Not-All-Equal 3-SAT (NAE 3SAT) (Boolean Satisfiability)}} == Description == NAE 3SAT restricts the boolean formula to CNF with 3 literals per clause and determines whether there is an assignment of variables such that, for none of the clauses, all 3 literals have the same boolean value == Related Problems == Generalizations: 3SAT Subproblem: Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) Related: SAT, Conjunctive Normal Form SAT, [...")
- 10:27, 15 February 2023 All-Equal-SAT (hist | edit) [839 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All-Equal-SAT (Boolean Satisfiability)}} == Description == All-Equal-SAT restricts the boolean formula to CNF and determines whether there is an assignment of variables such that, for all of the clauses, all literals have the same boolean value == Related Problems == Generalizations: Conjunctive Normal Form SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, Not-All-E...")
- 10:27, 15 February 2023 Monotone Not-Exactly-1-in-3SAT (hist | edit) [847 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone Not-Exactly-1-in-3SAT (Boolean Satisfiability)}} == Description == Monotone Not-Exactly-1-in-3SAT is Monotone 1-in-3SAT, except that rather than exactly one variable in a clause being true, it requires exactly 0, 2, or 3 of the variables in a clause being true == Related Problems == Generalizations: 1-in-3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, Monotone 1-in-3SAT, All-Equal-SAT, N...")
- 10:27, 15 February 2023 Monotone 1-in-3SAT (hist | edit) [824 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone 1-in-3SAT (Boolean Satisfiability)}} == Description == Monotone 1-in-3SAT is 1-in-3SAT with the restriction that all of the literals in a clause are all positive (note: here, we don't allow clauses to be all negated literals) == Related Problems == Generalizations: 1-in-3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE...")
- 10:27, 15 February 2023 1-in-3SAT (hist | edit) [896 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-in-3SAT (Boolean Satisfiability)}} == Description == 1-in-3SAT restricts the boolean formula to CNF with 3 literals per clause and determines whether there is an assignment of variables such that exactly 1 of the 3 literals in each clause is TRUE == Related Problems == Generalizations: 3SAT Subproblem: Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT,...")
- 10:27, 15 February 2023 Disjunctive Normal Form SAT (hist | edit) [755 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Disjunctive Normal Form SAT (Boolean Satisfiability)}} == Description == DNF-SAT restricts the boolean formula to disjunctive normal form (DNF), meaning it is the OR of ANDs. == Related Problems == Generalizations: SAT Related: Conjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-S...")
- 10:27, 15 February 2023 Conjunctive Normal Form SAT (hist | edit) [9,078 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Conjunctive Normal Form SAT (Boolean Satisfiability)}} == Description == CNF-SAT restricts the boolean formula to conjunctive normal form (CNF), meaning it is the AND of ORs. == Related Problems == Generalizations: SAT Subproblem: All-Equal-SAT, k-SAT, XOR-SAT, Horn SAT, MaxSAT Related: Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, Not-All-Equal 3-SAT (NAE 3S...")
- 10:27, 15 February 2023 SAT (hist | edit) [3,026 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:SAT (Boolean Satisfiability)}} == Description == Boolean satisfiability problems involve determining if there is an assignment of variables that satisfies a given boolean formula. == Related Problems == Subproblem: Conjunctive Normal Form SAT, Disjunctive Normal Form SAT Related: Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), [...")
- 10:27, 15 February 2023 Chromatic Polynomial (hist | edit) [31 bytes] Admin (talk | contribs) (Created page with "#REDIRECT #k-Graph Coloring")
- 10:26, 15 February 2023 5-Graph Coloring (hist | edit) [689 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:5-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 5-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 4-Graph Coloring (hist | edit) [1,659 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 4-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 3-Graph Coloring (hist | edit) [3,281 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 3-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 2-Graph Coloring (hist | edit) [578 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 2-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 Chromatic Number (hist | edit) [709 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Chromatic Number (Graph Coloring)}} == Description == In this case, we wish to compute the chromatic number of a graph; that is, the smallest number of colors needed to color the graph. == Related Problems == Related: k-Graph Coloring, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameter...")
- 10:26, 15 February 2023 K-Graph Coloring (hist | edit) [962 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-Graph Coloring (Graph Coloring)}} == Description == Graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In this case, the number of colors we have is given as an input. == Related Problems == Subproblem: 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring Related: Chromati...")
- 10:26, 15 February 2023 Link Analysis (hist | edit) [3,244 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Link Analysis (Link Analysis)}} == Description == Unlike "flat" document collections, the World Wide Web is hypertext and provides considerable auxiliary information on top of the text of the web pages, such as link structure and link text. With link analysis, we take advantage of the link structure of the Web to produce a global "importance" ranking of every web page that helps search engines and users quickly make sense of the vast heterogeneity of the...")
- 10:26, 15 February 2023 No-Steal/Force (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:No-Steal/Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal/No-Force == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 10:26, 15 February 2023 Steal/No-Force (hist | edit) [554 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Steal/No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal/Force == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem...")
- 10:26, 15 February 2023 Online (hist | edit) [2,107 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Online (Page Replacements)}} == Description == When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page. == Related Problems == Related: Offline == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Ap...")
- 10:26, 15 February 2023 Offline (hist | edit) [866 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Offline (Page Replacements)}} == Description == When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page. == Related Problems == Related: Online == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Ap...")
- 10:26, 15 February 2023 Dining Philosophers Problem (hist | edit) [1,486 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dining Philosophers Problem (Deadlock Avoidance)}} == Description == There are $n$ philosophers numbered 0 through $n-1$, seated around a circle table. Their only problem--besides philosophy--is that the dish served is a very difficult kind of spaghetti, that has to be eaten with two forks. There are two forks next to each plate, so that presents no difficulty: as a consequence, however, no two neighbors may be eating simultaneously. The philosophers' li...")
- 10:26, 15 February 2023 Deadlock Avoidance (hist | edit) [748 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Deadlock Avoidance (Deadlock Avoidance)}} == Description == A deadlock means that the processing of some parts, once started, cannot finish because each of these parts requests for its advancement some resource(s) currently held by some other part(s) in this set. In a deadlock avoidance approach, the controller must ensure that the granting of resources to any process will lead to a resulting state which is “safe,” i.e., a state from which all the p...")
- 10:26, 15 February 2023 Weighted Interval Schedule Maximization Problem (ISMP) (hist | edit) [567 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Weighted Interval Schedule Maximization Problem (ISMP) (Interval Scheduling)}} == Description == In Weighted Interval Scheduling, each interval has an associated weight. The goal is to maximize the weights of the accepted (and not interrupted) intervals. == Related Problems == Related: Unweighted Interval Scheduling == Parameters == <pre>n: number of tasks (intervals) k: number of machines (resources)</pre> == Table of Algorithms == Currentl...")
- 10:26, 15 February 2023 Unweighted Interval Scheduling (hist | edit) [2,931 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling (Interval Scheduling)}} == Description == Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise they ar...")
- 10:26, 15 February 2023 Polynomial Interpolation (hist | edit) [1,549 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Polynomial Interpolation (Polynomial Interpolation)}} == Description == Given a finite number of points $x_1, \ldots , x_n$, some real constants $y_1, \ldots , y_n$ and a subspace $V$ of $\Pi^d$, find a polynomial $p \in V$, such that $p(x_j) = y_j$, $j = 1, ... , n$ == Parameters == <pre>n: number of points d: dimension of space</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity grap...")
- 10:26, 15 February 2023 Block Ciphers (hist | edit) [1,395 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Block Ciphers (Block Ciphers)}} == Description == A block cipher is a pair of functions $E: \{0, 1\}^k \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ and $D: \{0, 1\}^k \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ that encode and decode a length $n$ string with a length $k$ key. == Parameters == <pre>n: text length (block size) k: key length</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Ye...")
- 10:26, 15 February 2023 Solutions to Nonlinear Equations (hist | edit) [1,307 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Solutions to Nonlinear Equations (Solutions to Nonlinear Equations)}} == Description == Compute the solutions to a given nonlinear equation of the form $f(x) = 0$. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Bisection method (Solutions to Nonlinear Equations Solutions to N...")
- 10:26, 15 February 2023 Secret Sharing (hist | edit) [1,127 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Secret Sharing (Secret Sharing)}} == Description == Secret Sharing is the splitting up of a secret amongst a group such that no individual can learn the entire secret alone, but when a sufficient amount of the group comes together with their parts of the secret, they can reconstruct the secret. == Parameters == <pre>n: size of the group the secret is being shared with</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:...")
- 10:26, 15 February 2023 Unkeyed Hash Functions (hist | edit) [1,908 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unkeyed Hash Functions (One-Way Hash Functions)}} == Description == A hash function, otherwise known as a one-way hash function, takes an arbitrary message of arbitrary length and creates an output (a hash) of a fixed length. The main characteristics of a cryptographic hash function are that given a message, it is easy to compute the hash; given the hash, it is difficult to compute the message; and that given a message, it is difficult to find a differen...")
- 10:26, 15 February 2023 Keyed Hash Functions (hist | edit) [1,062 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Keyed Hash Functions (One-Way Hash Functions)}} == Description == A hash function, otherwise known as a one-way hash function, takes an arbitrary message of arbitrary length and creates an output (a hash) of a fixed length. The main characteristics of a cryptographic hash function are that given a message, it is easy to compute the hash; given the hash, it is difficult to compute the message; and that given a message, it is difficult to find a different...")
- 10:26, 15 February 2023 Volterra Equations (hist | edit) [670 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Volterra Equations (Integral Equations)}} == Description == Integral equations are equations where an unknown function appears under an integral sign. Volterra equations have one limit of integration fixed while the other is a variable. == Related Problems == Related: Fredholm Equations == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Ti...")
- 10:26, 15 February 2023 Fredholm Equations (hist | edit) [691 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Fredholm Equations (Integral Equations)}} == Description == Integral equations are equations where an unknown function appears under an integral sign. Fredholm equations have both limits of integration fixed, and there are three types of Fredholm equations. == Related Problems == Related: Volterra Equations == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:26, 15 February 2023 The Frequent Words Problem (hist | edit) [1,059 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Frequent Words Problem (The Frequent Words Problem)}} == Description == Given a string of length $n$ and in input integer $k$, determine the most frequent $k$-mers in the string, i.e. the most frequent words of length $k$. == Parameters == <pre>n: length of string k: length of words sigma: size of alphabet</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! A...")