New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:20, 15 February 2023 APSP on Sparse Undirected Graphs with Positive Integer Weights (hist | edit) [1,731 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and has positive integer weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Grap...")
- 10:20, 15 February 2023 APSP on Sparse Directed Graphs with Arbitrary Weights (hist | edit) [1,046 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is directed, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on De...")
- 10:20, 15 February 2023 APSP on Dense Undirected Graphs with Positive Integer Weights (hist | edit) [1,731 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has positive integer weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Grap...")
- 10:20, 15 February 2023 APSP on Geometrically Weighted Graphs (hist | edit) [1,608 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Geometrically Weighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Dense Undirected Graph...")
- 10:20, 15 February 2023 APSP on Dense Undirected Graphs with Arbitrary Weights (hist | edit) [1,917 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, [...")
- 10:20, 15 February 2023 APSP on Dense Directed Graphs with Arbitrary Weights (hist | edit) [2,104 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is directed, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, A...")
- 10:19, 15 February 2023 APSP (hist | edit) [4,258 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP (All-Pairs Shortest Paths (APSP))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. == Related Problems == Subproblem: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirec...")
- 10:19, 15 February 2023 Replacement Paths Problem (hist | edit) [869 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Replacement Paths Problem (Shortest Path (Directed Graphs))}} == Description == Given nodes $s$ and $t$ in a weighted directed graph and a shortest path $P$ from $s$ to $t$, compute the length of the shortest simple path that avoids edge $e$, for all edges $e$ on $P$ == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-...")
- 10:19, 15 February 2023 2-sensitive decremental st-shortest paths (hist | edit) [1,349 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-sensitive decremental st-shortest paths (Shortest Path (Directed Graphs))}} == Description == Determine the st-shortest path with a sensitivity of 2 using decremental techniques. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-sho...")
- 10:19, 15 February 2023 1-sensitive decremental st-shortest paths (hist | edit) [1,748 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive decremental st-shortest paths (Shortest Path (Directed Graphs))}} == Description == Determine the st-shortest path with a sensitivity of 1 using decremental techniques. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-sho...")
- 10:19, 15 February 2023 2-sensitive (7/5)-approximate st-shortest paths (hist | edit) [1,332 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-sensitive (7/5)-approximate st-shortest paths (Shortest Path (Directed Graphs))}} == Description == Approximate the st-shortest paths problem within a factor of 7/5 with a sensitivity of 2. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 1-sensitive decremental s...")
- 10:19, 15 February 2023 1-sensitive (3/2)-approximate ss-shortest paths (hist | edit) [1,326 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive (3/2)-approximate ss-shortest paths (Shortest Path (Directed Graphs))}} == Description == Approximate the single source shortest paths problem within a factor of 3/2 with a sensitivity of 1. == Related Problems == Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, st-Shortest Path, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensitive decremental st-shor...")
- 10:19, 15 February 2023 St-Shortest Path (hist | edit) [957 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:st-Shortest Path (Shortest Path (Directed Graphs))}} == Description == Given a weighted digraph $G=(V,E)$, find the shortest path between two given vertices $s$ and $t$. == Related Problems == Subproblem: Second Shortest Simple Path, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensitive decremental st-shortest paths, 2-sensitive decremental st-shortest paths, Replacement Paths Problem Related: General Weights, Non...")
- 10:19, 15 February 2023 Second Shortest Simple Path (hist | edit) [2,123 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Second Shortest Simple Path (Shortest Path (Directed Graphs))}} == Description == Given a weighted digraph $G=(V,E)$, find the second shortest path between two given vertices $s$ and $t$. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensiti...")
- 10:19, 15 February 2023 Nonnegative Integer Weights (hist | edit) [2,175 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Nonnegative Integer Weights (Shortest Path (Directed Graphs))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Here, the weights are restricted to be nonnegative integers. == Related Problems == Generalizations: nonnegative weights Related: General Weights, Nonnegative Weights, Second Shortest...")
- 10:19, 15 February 2023 Nonnegative Weights (hist | edit) [2,754 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Nonnegative Weights (Shortest Path (Directed Graphs))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Here, the weights are restricted to be nonnegative. == Related Problems == Generalizations: general weights Subproblem: Nonnegative Integer Weights Related: General Weights, Second Shortest S...")
- 10:19, 15 February 2023 General Weights (hist | edit) [892 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Weights (Shortest Path (Directed Graphs))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Here, the weights can be any real number. == Related Problems == Subproblem: Nonnegative Weights Related: Nonnegative Integer Weights, Second Shortest Simple Path, st-Shortest Path, 1-sensitiv...")
- 10:19, 15 February 2023 2-dimensional array representation (hist | edit) [1,207 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional array representation (Closest Pair Problem)}} == Description == Given $n$ points in 2-dimensional space in array representation, find a pair of points with the smallest distance between them. == Related Problems == Related: k-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional space, Euclidean metric == Parameters == No parameters found. == Table of Algorithms ==...")
- 10:19, 15 February 2023 2-dimensional space, Euclidean metric (hist | edit) [1,306 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional space, Euclidean metric (Closest Pair Problem)}} == Description == Given $n$ points in 2-dimensional space equipped with the Eucildean metric, find a pair of points with the smallest distance between them. == Related Problems == Related: k-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional array representation == Parameters == No parameters found. == Table of Alg...")
- 10:19, 15 February 2023 2-dimensional space, $l m$ (or $l \infty$) norm (hist | edit) [1,002 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional space, $l_m$ (or $l_\infty$) norm (Closest Pair Problem)}} == Description == Given $n$ points in 2-dimensional space equipped with the $l_m$ (or $l_\infty$) norm, find a pair of points with the smallest distance between them. == Related Problems == Generalizations: k-dimensional space, $l_m$ (or $l_\infty$) norm Related: 2-dimensional space, Euclidean metric, 2-dimensional array representation == Parameters == No paramet...")
- 10:19, 15 February 2023 K-dimensional space, $l m$ (or $l \infty$) norm (hist | edit) [1,019 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-dimensional space, $l_m$ (or $l_\infty$) norm (Closest Pair Problem)}} == Description == Given $n$ points in metric space, typically $k$-dimensional space equipped with $l_m$ (or $l_\infty$) norm, find a pair of points with the smallest distance between them. == Related Problems == Subproblem: 2-dimensional space, $l_m$ (or $l_\infty$) norm Related: 2-dimensional space, Euclidean metric, 2-dimensional array representation == Parameter...")
- 10:19, 15 February 2023 Directed (Optimum Branchings), Super Dense MST (hist | edit) [1,378 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Directed (Optimum Branchings), Super Dense MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we're given a directed graph with a root and $E=\Omega(V^2)$ edges, and we wish to find a spanning arborescence...")
- 10:19, 15 February 2023 Directed (Optimum Branchings), General MST (hist | edit) [2,137 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Directed (Optimum Branchings), General MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we're given a directed graph with a root, and we wish to find a spanning arborescence of minimum weight that is root...")
- 10:19, 15 February 2023 Undirected, Integer Weights MST (hist | edit) [1,285 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, Integer Weights MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we assume that the edges have integer weights, represented in binary. == Related Problems == Generalizations: Undirected,...")
- 10:19, 15 February 2023 Undirected, Planar MST (hist | edit) [1,206 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, Planar MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we assume that the graph is planar. == Related Problems == Generalizations: Undirected, General MST Related: Undirected, Dense...")
- 10:19, 15 February 2023 Undirected, Dense MST (hist | edit) [1,226 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, Dense MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we assume that the graph is dense (i.e. $E = \Omega(V)$). == Related Problems == Generalizations: Undirected, General MST Related...")
- 10:19, 15 February 2023 Undirected, General MST (hist | edit) [5,489 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, General MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, there are no restrictions on edge weights or graph density. == Related Problems == Subproblem: Undirected, Dense MST, Undirec...")
- 10:19, 15 February 2023 Connected Subgraph (hist | edit) [744 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Connected Subgraph (Strongly Connected Components)}} == Description == Subgraph connectivity asks us to maintainan understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) == Related Problems == Related: Strongly Connected Components, Transitive Closure,...")
- 10:19, 15 February 2023 2 Strong Components (dynamic) (hist | edit) [1,193 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2 Strong Components (dynamic) (Strongly Connected Components)}} == Description == maintain: a directed graph, under: edge insertion/deletions, answer: are there more than 2 strongly connected components? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Maximum Strongly Connected Component, Strong Connectivity (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algori...")
- 10:19, 15 February 2023 Strong Connectivity (dynamic) (hist | edit) [1,263 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Strong Connectivity (dynamic) (Strongly Connected Components)}} == Description == maintain: a directed graph, under edge insertions/deletions, answer: is the graph strongly connected? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Maximum Strongly Connected Component, 2 Strong Components (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algorithms == Currently...")
- 10:19, 15 February 2023 Maximum Strongly Connected Component (hist | edit) [557 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Strongly Connected Component (Strongly Connected Components)}} == Description == maintain: a directed graph, under: edge insertions/deletions, answer: what is the size of the largest SCC? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Strong Connectivity (dynamic), 2 Strong Components (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algorithms == Curre...")
- 10:19, 15 February 2023 Transitive Closure (hist | edit) [1,060 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Transitive Closure (Strongly Connected Components)}} == Description == In this problem, we also want to compute the transitive closure of a graph. (Perhaps this should be a separate problem?) == Related Problems == Related: Strongly Connected Components, Maximum Strongly Connected Component, Strong Connectivity (dynamic), 2 Strong Components (dynamic), Connected Subgraph == Parameters == <pre>V: number of vertices E: number of e...")
- 10:19, 15 February 2023 2-dimensional Convex Hull, Dynamic (hist | edit) [1,411 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull, Dynamic (Convex Hull)}} == Description == Here, the input points may be sequentially inserted or deleted, and the convex hull must be updated after each insert/delete operation. == Related Problems == Generalizations: 2-dimensional Convex Hull Related: 3-dimensional Convex Hull, d-dimensional Convex Hull, 2-dimensional Convex Hull, Online == Parameters == <pre>n: number of line segments h: number of point...")
- 10:19, 15 February 2023 2-dimensional Convex Hull, Online (hist | edit) [1,340 bytes] Admin (talk | contribs) (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</...")
- 10:19, 15 February 2023 D-dimensional Convex Hull (hist | edit) [1,690 bytes] Admin (talk | contribs) (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...")
- 10:19, 15 February 2023 3-dimensional Convex Hull (hist | edit) [932 bytes] Admin (talk | contribs) (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...")
- 10:19, 15 February 2023 2-dimensional Convex Hull (hist | edit) [1,996 bytes] Admin (talk | contribs) (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...")
- 10:19, 15 February 2023 Counting number of intersection points, line segments (hist | edit) [792 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Reporting all intersection points, general polygons (hist | edit) [811 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Reporting all intersection points, convex polygons (hist | edit) [1,428 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Reporting all intersection points, generalized segments (hist | edit) [1,961 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Reporting all intersection points, line segments (hist | edit) [2,457 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 0-1 Linear Programming (hist | edit) [3,138 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Integer Linear Programming (hist | edit) [3,145 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Linear Programming with Reals (hist | edit) [3,212 bytes] Admin (talk | contribs) (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"...")
- 10:18, 15 February 2023 General Linear Programming (hist | edit) [3,395 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Vandermonde Matrix (hist | edit) [1,246 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Toeplitz Matrix (hist | edit) [1,569 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Non-Definite, Symmetric Matrix (hist | edit) [1,286 bytes] Admin (talk | contribs) (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...")
- 10:18, 15 February 2023 Positive Definite, Hermitian Matrix (hist | edit) [1,494 bytes] Admin (talk | contribs) (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...")