User contributions for Admin

15 February 2023

• 11:1911:19, 15 February 2023 diff hist +1,345‎ N 2-dimensional Convex Hull, Online ‎ Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull, Online (Convex Hull)}} == Description == Here, we are given the input points one by one, and must maintain the current convex hull after each input point. == Related Problems == Generalizations: 2-dimensional Convex Hull Related: 3-dimensional Convex Hull, d-dimensional Convex Hull, 2-dimensional Convex Hull, Dynamic == Parameters == <pre>n: number of line segments h: number of points on the convex hull</..."
• 11:1911:19, 15 February 2023 diff hist +1,689‎ N D-dimensional Convex Hull ‎ Created page with "{{DISPLAYTITLE:d-dimensional Convex Hull (Convex Hull)}} == Description == Here, we are looking at the general d-dimensional case. == Related Problems == Subproblem: 2-dimensional Convex Hull, 3-dimensional Convex Hull Related: 3-dimensional Convex Hull, 2-dimensional Convex Hull, Online, 2-dimensional Convex Hull, Dynamic == Parameters == <pre>n: number of line segments h: number of points on the convex hull f_1: number of facets on the con..."
• 11:1911:19, 15 February 2023 diff hist +937‎ N 3-dimensional Convex Hull ‎ Created page with "{{DISPLAYTITLE:3-dimensional Convex Hull (Convex Hull)}} == Description == Here, we are looking at the 3-dimensional case. == Related Problems == Generalizations: d-dimensional Convex Hull Related: 2-dimensional Convex Hull, 2-dimensional Convex Hull, Online, 2-dimensional Convex Hull, Dynamic == Parameters == <pre>n: number of line segments h: number of points on the convex hull</pre> == Table of Algorithms == {| class="wikitable sortable" s..."
• 11:1911:19, 15 February 2023 diff hist +1,252‎ N 2-dimensional Convex Hull ‎ Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull (Convex Hull)}} == Description == The convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or; more generally; in an affine space over the reals) is the smallest convex set that contains X. Here, we are looking at the 2-dimensional case. == Related Problems == Generalizations: d-dimensional Convex Hull Subproblem: 2-dimensional Convex Hull, Online, 2..."
• 11:1911:19, 15 February 2023 diff hist +798‎ N Counting number of intersection points, line segments ‎ Created page with "{{DISPLAYTITLE:Counting number of intersection points, line segments (Line segment intersection)}} == Description == In this case, we are supplied with a list of line segments, and we wish to count the number of points of intersection. == Related Problems == Generalizations: Reporting all intersection points, line segments Related: Reporting all intersection points, generalized segments, Reporting all intersection points, convex polygons, Reporting al..."
• 11:1811:18, 15 February 2023 diff hist +817‎ N Reporting all intersection points, general polygons ‎ Created page with "{{DISPLAYTITLE:Reporting all intersection points, general polygons (Line segment intersection)}} == Description == In this case, we are supplied with a list of polygons (not necessarily convex), and we wish to report all regions of intersection. == Related Problems == Subproblem: Reporting all intersection points, convex polygons Related: Reporting all intersection points, line segments, Reporting all intersection points, generalized segments, Countin..."
• 11:1811:18, 15 February 2023 diff hist +1,718‎ N Reporting all intersection points, convex polygons ‎ Created page with "{{DISPLAYTITLE:Reporting all intersection points, convex polygons (Line segment intersection)}} == Description == In this case, we are supplied with a list of convex polygons, and we wish to report all regions of intersection. == Related Problems == Generalizations: Reporting all intersection points, general polygons Related: Reporting all intersection points, line segments, Reporting all intersection points, generalized segments, Counting number of i..."
• 11:1811:18, 15 February 2023 diff hist +2,260‎ N Reporting all intersection points, generalized segments ‎ Created page with "{{DISPLAYTITLE:Reporting all intersection points, generalized segments (Line segment intersection)}} == Description == In this case, the segments are generalized (i.e. have algebraic degree ≥1); we still wish to report all points of intersection. == Related Problems == Subproblem: Reporting all intersection points, line segments Related: Reporting all intersection points, convex polygons, Reporting all intersection points, general polygons, Counting..."
• 11:1811:18, 15 February 2023 diff hist +2,807‎ N Reporting all intersection points, line segments ‎ Created page with "{{DISPLAYTITLE:Reporting all intersection points, line segments (Line segment intersection)}} == Description == The line segment intersection problem supplies a list of line segments in the Euclidean plane and asks about the points where they intersect (cross), if any. In this case, we wish to report all points of intersection. == Related Problems == Generalizations: Reporting all intersection points, generalized segments Subproblem: Counting number of inters..."
• 11:1811:18, 15 February 2023 diff hist +3,184‎ N 0-1 Linear Programming ‎ Created page with "{{DISPLAYTITLE:0-1 Linear Programming (Linear Programming)}} == Description == In this case, we require all of the variables to be either 0 or 1. == Related Problems == Generalizations: Integer Linear Programming Related: General Linear Programming, Linear Programming with Reals == Parameters == <pre>n: number of variables m: number of constraints L: length of input, in bits</pre> == Table of Algorithms == {| class="wikitable sortable" style="tex..."
• 11:1811:18, 15 February 2023 diff hist +40‎ N ILP ‎ Redirected page to Integer Linear Programming current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +3,191‎ N Integer Linear Programming ‎ Created page with "{{DISPLAYTITLE:Integer Linear Programming (Linear Programming)}} == Description == In this case, we require all of the variables to be integers. == Related Problems == Generalizations: Linear Programming with Reals Subproblem: 0-1 Linear Programming Related: General Linear Programming == Parameters == <pre>n: number of variables m: number of constraints L: length of input, in bits</pre> == Table of Algorithms == {| class="wikitable sortable" sty..."
• 11:1811:18, 15 February 2023 diff hist +3,258‎ N Linear Programming with Reals ‎ Created page with "{{DISPLAYTITLE:Linear Programming with Reals (Linear Programming)}} == Description == In this case, we allow all of the variables to be any real number. == Related Problems == Generalizations: General Linear Programming Subproblem: Integer Linear Programming Related: 0-1 Linear Programming == Parameters == <pre>n: number of variables m: number of constraints L: length of input, in bits</pre> == Table of Algorithms == {| class="wikitable sortable"..."
• 11:1811:18, 15 February 2023 diff hist +3,441‎ N General Linear Programming ‎ Created page with "{{DISPLAYTITLE:General Linear Programming (Linear Programming)}} == Description == Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). == Related Problems == Subproblem: Linear Programming wi..."
• 11:1811:18, 15 February 2023 diff hist +1,171‎ N Vandermonde Matrix ‎ Created page with "{{DISPLAYTITLE:Vandermonde Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be a Vandermonde matrix. == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Toeplitz Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k: ratio between largest and sma..."
• 11:1811:18, 15 February 2023 diff hist +1,488‎ N Toeplitz Matrix ‎ Created page with "{{DISPLAYTITLE:Toeplitz Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be a Toeplitz matrix. == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k: ratio between largest and smalle..."
• 11:1811:18, 15 February 2023 diff hist +1,235‎ N Non-Definite, Symmetric Matrix ‎ Created page with "{{DISPLAYTITLE:Non-Definite, Symmetric Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be non-definite and symmetric. == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Toeplitz Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k: ratio between largest a..."
• 11:1811:18, 15 February 2023 diff hist +1,222‎ N Positive Definite, Hermitian Matrix ‎ Created page with "{{DISPLAYTITLE:Positive Definite, Hermitian Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be positive definite and hermitian (or symmetric, if $A$ is real-valued). == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Non-Definite, Symmetric Matrix, Toeplitz Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero e..."
• 11:1811:18, 15 February 2023 diff hist +1,042‎ N Sparse Linear System ‎ Created page with "{{DISPLAYTITLE:Sparse Linear System (Linear System)}} == Description == In this case, we restrict $A$ to be sparse (i.e. $A$ only has $O(n)$ nonzero entries). == Related Problems == Generalizations: General Linear System Related: Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Toeplitz Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k:..."
• 11:1811:18, 15 February 2023 diff hist +1,225‎ N General Linear System ‎ Created page with "{{DISPLAYTITLE:General Linear System (Linear System)}} == Description == A system of linear equations (or linear system) is a collection of one or more linear equations involving the same set of variables. This is typically written in the form $Ax=b$ where $A$ is a matrix and $x, b$ are vectors. In this case, we impose no restrictions on $A$. == Related Problems == Subproblem: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symme..."
• 11:1811:18, 15 February 2023 diff hist +36‎ N $(\min, \leq)$ Matrix Multiplication ‎ Redirected page to $(\min, \leq)$ Product current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +963‎ N $(\min, \leq)$ Product ‎ Created page with "{{DISPLAYTITLE:$(\min, \leq)$ Product (Matrix Product)}} == Description == Matrix product over the $(\min, \leq)$-semiring == Related Problems == Related: Matrix Multiplication, Boolean Matrix Multiplication, Boolean Matrix Multiplication (Combinatorial), Matrix Product Verification, Distance Product == Parameters == <pre>n: dimension of square matrix</pre> == Table of Algorithms == Currently no algorithms in our database for the given prob..."
• 11:1811:18, 15 February 2023 diff hist +30‎ N Funny Matrix Multiplication ‎ Redirected page to Distance Product current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +30‎ N $(\min, +)$ Matrix Product ‎ Redirected page to Distance Product current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +30‎ N $(\min, +)$ Matrix Multiplication ‎ Redirected page to Distance Product current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +1,504‎ N Distance Product ‎ Created page with "{{DISPLAYTITLE:Distance Product (Matrix Product)}} == Description == Matrix product over the $(\min, +)$-semiring == Related Problems == Related: Matrix Multiplication, Boolean Matrix Multiplication, Boolean Matrix Multiplication (Combinatorial), Matrix Product Verification, $(\min, \leq)$ Product == Parameters == <pre>n: dimension of square matrix</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem..."
• 11:1811:18, 15 February 2023 diff hist +999‎ N Matrix Product Verification ‎ Created page with "{{DISPLAYTITLE:Matrix Product Verification (Matrix Product)}} == Description == Given three matrices $A, B, C$, verify that $AB = C$, i.e. that $C$ is the matrix product of $A$ and $B$ == Related Problems == Generalizations: Matrix Multiplication Related: Boolean Matrix Multiplication, Boolean Matrix Multiplication (Combinatorial), Distance Product, $(\min, \leq)$ Product == Parameters == <pre>n: dimension of square matrix</pre> == Table of..."
• 11:1811:18, 15 February 2023 diff hist +59‎ N BMM (Combinatorial) ‎ Redirected page to Boolean Matrix Multiplication (Combinatorial) current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +2,542‎ N Boolean Matrix Multiplication (Combinatorial) ‎ Created page with "{{DISPLAYTITLE:Boolean Matrix Multiplication (Combinatorial) (Matrix Product)}} == Description == Matrix multiplication of two boolean matrices (i.e. where all entries are in $F_2$ and addition is mod 2). Here, only "combinatorial" algorithms are considered. == Related Problems == Generalizations: Boolean Matrix Multiplication Related: Matrix Multiplication, Matrix Product Verification, Distance Product, $(\min, \leq)$ Product == Parameters ==..."
• 11:1811:18, 15 February 2023 diff hist +43‎ N And-or Matrix Product ‎ Redirected page to Boolean Matrix Multiplication current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +43‎ N BMM ‎ Redirected page to Boolean Matrix Multiplication current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +6,184‎ N Boolean Matrix Multiplication ‎ Created page with "{{DISPLAYTITLE:Boolean Matrix Multiplication (Matrix Product)}} == Description == Matrix multiplication of two boolean matrices (i.e. where all entries are in $F_2$ and addition is mod 2) == Related Problems == Generalizations: Matrix Multiplication Subproblem: Boolean Matrix Multiplication (Combinatorial) Related: Matrix Product Verification, Distance Product, $(\min, \leq)$ Product == Parameters == <pre>n: dimension of square matrix</pre>..."
• 11:1811:18, 15 February 2023 diff hist +1,647‎ Matrix Multiplication ‎No edit summary
• 11:1811:18, 15 February 2023 diff hist +6,050‎ N Maximum Local Edge Connectivity ‎ Created page with "{{DISPLAYTITLE:Maximum Local Edge Connectivity (Maximum Flow)}} == Description == Find the pair of nodes with the maximum number of edge-disjoint paths between them == Related Problems == Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow == Parameters == <pre>V: number of vertices E: number of edges</pre> == Table of Algorithms == {| class="wikita..."
• 11:1811:18, 15 February 2023 diff hist +6,428‎ N All-Pairs Maximum Flow ‎ Created page with "{{DISPLAYTITLE:All-Pairs Maximum Flow (Maximum Flow)}} == Description == Find the maximum flow between all pairs of nodes == Related Problems == Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of vertices E: number of edges</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:c..."
• 11:1811:18, 15 February 2023 diff hist +31‎ N MCF ‎ Redirected page to Minimum-Cost Flow current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +5,731‎ N Minimum-Cost Flow ‎ Created page with "{{DISPLAYTITLE:Minimum-Cost Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, each edge is given a cost coefficient, and we wish to minimize total cost while reaching a threshold flow. == Related Problems == Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, All-Pairs Maximum Flow, Maximum Local Ed..."
• 11:1811:18, 15 February 2023 diff hist +5,576‎ N Non-integer Maximum Flow ‎ Created page with "{{DISPLAYTITLE:Non-integer Maximum Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities may be non-integers. == Related Problems == Subproblem: Integer Maximum Flow Related: st-Maximum Flow, Unweighted Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of ver..."
• 11:1811:18, 15 February 2023 diff hist +5,610‎ N Unweighted Maximum Flow ‎ Created page with "{{DISPLAYTITLE:Unweighted Maximum Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, all edges have unit weight. == Related Problems == Generalizations: Integer Maximum Flow Related: st-Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of vertic..."
• 11:1811:18, 15 February 2023 diff hist +6,862‎ N Integer Maximum Flow ‎ Created page with "{{DISPLAYTITLE:Integer Maximum Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities must be integers. == Related Problems == Generalizations: Non-Integer Maximum Flow Subproblem: Unweighted Maximum Flow Related: st-Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity..."
• 11:1811:18, 15 February 2023 diff hist +7,997‎ N St-Maximum Flow ‎ Created page with "{{DISPLAYTITLE:st-Maximum Flow (Maximum Flow)}} == Description == Find the maximum flow from $s$ to $t$ == Related Problems == Related: Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of vertices E: number of edges U: maximum edge capacity</pre> == Table of Algorithms == {| class="wikitable sortable" style..."
• 11:1811:18, 15 February 2023 diff hist +1,363‎ N Longest Common Substring with don't cares ‎ Created page with "{{DISPLAYTITLE:Longest Common Substring with don't cares (Longest Common Subsequence)}} == Description == Find the length of the longest common substring of two strings S and T, where S is a binary string and T is is a binary string and additional * characters that can match either 0 or 1. == Related Problems == Generalizations: Longest Common Subsequence == Parameters == <pre>$n$: length of the longer input string $m$: length of the shorter input string $r$:..."
• 11:1811:18, 15 February 2023 diff hist +40‎ N LCS ‎ Redirected page to Longest Common Subsequence current Tag: New redirect
• 11:1811:18, 15 February 2023 diff hist +1,566‎ N Longest Common Subsequence ‎ Created page with "{{DISPLAYTITLE:Longest Common Subsequence (Longest Common Subsequence)}} == Description == The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). == Related Problems == Subproblem: Longest Common Substring with don't cares == Parameters == <pre>$n$: length of the longer input string $m$: length of the shorter input string $r$: length of the LCS $s..."
• 11:1711:17, 15 February 2023 diff hist +1,387‎ N Approximate MCSP ‎ Created page with "{{DISPLAYTITLE:Approximate MCSP (Matrix Chain Multiplication)}} == Description == The Matrix Chain Scheduling Problem (or MCSP) is an optimization problem� where the goal is to find the product sequence for evaluating a chain of matrix products and the processor schedule for the sequence such that the evaluation time is minimized on a parallel system. In the approximation problem, the matrix multiplication carried out with the output result will use a number of opera..."
• 11:1711:17, 15 February 2023 diff hist +45‎ N MCSP ‎ Redirected page to Matrix Chain Scheduling Problem current Tag: New redirect
• 11:1711:17, 15 February 2023 diff hist +1,221‎ N Matrix Chain Scheduling Problem ‎ Created page with "{{DISPLAYTITLE:Matrix Chain Scheduling Problem (Matrix Chain Multiplication)}} == Description == The Matrix Chain Scheduling Problem (or MCSP) is an optimization problem� where the goal is to find the product sequence for evaluating a chain of matrix products and the processor schedule for the sequence such that the evaluation time is minimized on a parallel system. == Related Problems == Generalizations: Matrix Chain Ordering Problem Subproblem: Approximat..."
• 11:1711:17, 15 February 2023 diff hist +2,023‎ N Approximate MCOP ‎ Created page with "{{DISPLAYTITLE:Approximate MCOP (Matrix Chain Multiplication)}} == Description == Matrix chain multiplication (or Matrix Chain Ordering Problem; MCOP) is an optimization problem. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. In the approximation problem, the matrix multiplication carried out with the output result will use a number of operations that has some sort of upper bound based on the optimal solution. == R..."
• 11:1711:17, 15 February 2023 diff hist +43‎ N MCOP ‎ Redirected page to Matrix Chain Ordering Problem current Tag: New redirect
• 11:1711:17, 15 February 2023 diff hist +1,798‎ N Matrix Chain Ordering Problem ‎ Created page with "{{DISPLAYTITLE:Matrix Chain Ordering Problem (Matrix Chain Multiplication)}} == Description == Matrix chain multiplication (or Matrix Chain Ordering Problem; MCOP) is an optimization problem. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. == Related Problems == Subproblem: Approximate MCOP, Matrix Chain Scheduling Problem Related: Matrix Chain Scheduling Problem, Approximate MCSP == Parameters..."