New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:25, 15 February 2023 Pattern Matching on Hypertext (hist | edit) [41 bytes] Admin (talk | contribs) (Redirected page to Sequence-To-Graph Alignment) Tag: New redirect
- 10:25, 15 February 2023 Sequence-To-Graph Alignment (hist | edit) [1,162 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Sequence-To-Graph Alignment (Sequence-to-Graph Alignment)}} == Description == This is pattern matching where you are given a pattern and a hypertext graph. The hypertext model is that the text forms a graph of $N$ nodes and $E$ edges, where a string is stored inside each node, and the edges indicate alternative texts that may follow the current node. The pattern is still a simple string of length $m$. It is also customary to transform this graph into a o...")
- 10:25, 15 February 2023 Integer Relation Among Integers (hist | edit) [790 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Relation Among Integers (Integer Relation)}} == Description == Given a vector $x \in \mathbb{Z}^n$, find an integer relation, i.e. a non-zero vector $m \in \mathbb{Z}^n$ such that $<x, m> = 0$ == Related Problems == Generalizations: Integer Relation Among Reals == Parameters == <pre>n: dimensionality of vectors</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Ti...")
- 10:25, 15 February 2023 Integer Relation Among Reals (hist | edit) [785 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Relation Among Reals (Integer Relation)}} == Description == Given a vector $x \in \mathbb{R}^n$, find an integer relation, i.e. a non-zero vector $m \in \mathbb{Z}^n$ such that $<x, m> = 0$ == Related Problems == Subproblem: Integer Relation Among Integers == Parameters == <pre>n: dimensionality of vectors</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !!...")
- 10:25, 15 February 2023 Determinant of Matrices with Integer Entries (hist | edit) [1,238 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Determinant of Matrices with Integer Entries (Determinant of Matrices with Integer Entries)}} == Description == Calculate the determinant of a given matrix with integer matrices. For such matrices, the determinant is also an integer. == Parameters == <pre>n: dimension of matrix</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! R...")
- 10:25, 15 February 2023 Undirected Wiener Index (hist | edit) [977 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected Wiener Index (Wiener Index)}} == Description == Calculate the sum of the lengths of the shortest paths between all pairs of vertices in an undirected graph (typically in the chemical graph representing the non-hydrogen atoms in the molecule). == Related Problems == Related: Minimum Wiener Connector Problem == Parameters == <pre>n: number of vertices (number of non-hydrogen atoms in the molecule)</pre> == Table of Algorithms == Cur...")
- 10:25, 15 February 2023 Minimum Wiener Connector Problem (hist | edit) [629 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum Wiener Connector Problem (Wiener Index)}} == Description == Given a connected graph $G = (V, E)$ and a set $Q \subseteq V$ of query vertices, find a subgraph of $G$ that connects all query vertices and has minimum Wiener index. == Related Problems == Related: Undirected Wiener Index == Parameters == <pre>n: number of vertices m: number of edges q: number of query vertices</pre> == Table of Algorithms == Currently no algorithms in our...")
- 10:25, 15 February 2023 Max Cut (hist | edit) [25 bytes] Admin (talk | contribs) (Redirected page to Maximum Cut) Tag: New redirect
- 10:25, 15 February 2023 Maximum Cut (hist | edit) [1,989 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Cut (Maximum Cut)}} == Description == Given a graph $G=(V, E)$ with edge weights $c_e > 0$ for all $e\in E$, find a cut $\delta(W)$ such that $c(\delta(W)):=\Sigma_{e\in \dela(W)} c_e$ is as large as possible. == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !!...")
- 10:25, 15 February 2023 D-Neighborhood of a String (hist | edit) [978 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:d-Neighborhood of a String (d-Neighborhood of a String)}} == Description == Given a DNA string pattern and an integer $d$, find the collection of strings that are within a $d$-neighborhood of the given pattern. A $d$-neighborhood is the set of all $k$-mers whose Hamming distance from the pattern is at most $d$. == Parameters == <pre>n: length of string d: neighborhood distance threshold sigma: size of alphabet</pre> == Table of Algorithms == {| cla...")
- 10:25, 15 February 2023 SLAM Algorithms (hist | edit) [1,790 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:SLAM Algorithms (SLAM Algorithms)}} == Description == Simultaneous localization and mapping (SLAM) is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent's location within it. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !!...")
- 10:25, 15 February 2023 OGM (hist | edit) [36 bytes] Admin (talk | contribs) (Redirected page to Occupancy Grid Mapping) Tag: New redirect
- 10:25, 15 February 2023 Occupancy Grid Mapping (hist | edit) [1,060 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Occupancy Grid Mapping (Occupancy Grid Mapping)}} == Description == Assuming a robot's pose is known, generate a occupancy grid mapping of the area. The occupancy grid is a multidimensional random field that maintains stochastic estimates of the occupancy state of the cells in a spatial lattice. To construct a sensor-derived map of the robot’s world, the cell state estimates are obtained by interpreting the incoming range readings using probabilistic s...")
- 10:25, 15 February 2023 Illumination Mapping (hist | edit) [33 bytes] Admin (talk | contribs) (Redirected page to Environment Mapping) Tag: New redirect
- 10:25, 15 February 2023 Reflection Mapping (hist | edit) [33 bytes] Admin (talk | contribs) (Redirected page to Environment Mapping) Tag: New redirect
- 10:25, 15 February 2023 Environment Mapping (hist | edit) [1,914 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Environment Mapping (Texture Mapping)}} == Description == Texture mapping means the mapping of a function onto a surface in 3D. The domain of the function can be one, two, or three dimensional, and it can be represented by either an array or a mathematical function. The source image (texture) is mapped onto a surface in 3D object space, which is then mapped to the destination image (screen) by the viewing projection. Texture space is labeled $(u, v)$, o...")
- 10:25, 15 February 2023 Rasterization (hist | edit) [908 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rasterization (Rasterization)}} == Description == Raster-scan displays are most commonly driven by a frame buffer, a memory that stores the color value for every picture element on the screen and refreshes the display continuously. The process of generating these picture clement values from a geometric description of the image is known as rasterization. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" s...")
- 10:25, 15 February 2023 Partially Observable Markov Decision Process (hist | edit) [20 bytes] Admin (talk | contribs) (Redirected page to POMDPs) Tag: New redirect
- 10:25, 15 February 2023 POMDPs (hist | edit) [2,598 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:POMDPs (POMDPs)}} == Description == At (discrete) time step $t$, the environment is assumed to be in some state $X_t$. The agent then performs an action (control) $A_t$, whereupon the environment (stochastically) changes to a new state $X_{t+1}$. The agent doesn’t see the environment state, but instead receives an observation $Y_t$, which is some (stochastic) function of $X_t$. (If $Y_t = X_t$, the POMDP reduces to a fully observed MDP.) In addition, t...")
- 10:25, 15 February 2023 Clock Synchronization in Distributed Systems (hist | edit) [1,552 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Clock Synchronization in Distributed Systems (Clock Synchronization in Distributed Systems)}} == Description == The difference between the largest and the smallest clock values among all stations in a Mobile Ad Hoc Network (MANET) is called the maximum clock offset. The goal is to minimize the maximum clock offset. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:25, 15 February 2023 Mesh Simplification (hist | edit) [4,955 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Mesh Simplification (Mesh Simplification)}} == Description == Given a surface mesh, accurately simplify it so that you may render the mesh accurately with less computing power. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Coplanar facets merging - M.J. De Haemer and M.J. Zy...")
- 10:25, 15 February 2023 Image Segmentation (hist | edit) [3,924 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Image Segmentation (Image Segmentation)}} == Description == Image segmentation is the division of an image into different regions, each having certain properties. It is the first step of image analysis which aims at either a description of an image or a classification of the image if a class label is meaningful. An example of the former is the description of an office scene. An example of the latter is the classification of the image of a cancerous cell....")
- 10:25, 15 February 2023 Point-in-Polygon (hist | edit) [2,488 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Point-in-Polygon (Point-in-Polygon)}} == Description == With a given polygon $P$ and an arbitrary point $q$, determine whether point $q$ is enclosed by the edges of the polygon. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Ray casting algorithm Shimrat; M (Point-in-Polygon...")
- 10:25, 15 February 2023 Specular Reflection (hist | edit) [1,646 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Specular Reflection (Texture Mapping)}} == Description == Texture mapping means the mapping of a function onto a surface in 3D. The domain of the function can be one, two, or three dimensional, and it can be represented by either an array or a mathematical function. The source image (texture) is mapped onto a surface in 3D object space, which is then mapped to the destination image (screen) by the viewing projection. Texture space is labeled $(u, v)$, o...")
- 10:25, 15 February 2023 Diffuse Reflection (hist | edit) [2,186 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Diffuse Reflection (Texture Mapping)}} == Description == Texture mapping means the mapping of a function onto a surface in 3D. The domain of the function can be one, two, or three dimensional, and it can be represented by either an array or a mathematical function. The source image (texture) is mapped onto a surface in 3D object space, which is then mapped to the destination image (screen) by the viewing projection. Texture space is labeled $(u, v)$, ob...")
- 10:25, 15 February 2023 CPSP (hist | edit) [47 bytes] Admin (talk | contribs) (Redirected page to Cyclic Peptide Sequencing Problem) Tag: New redirect
- 10:25, 15 February 2023 Cyclic Peptide Sequencing Problem (hist | edit) [1,000 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Cyclic Peptide Sequencing Problem (Cyclic Peptide Sequencing Problem)}} == Description == Given an experimental $MS^3$ spectrum $S$, find a cyclic peptide $P$ maximizing the number of shared masses between $S$ and the theoretical spectrum of $P$. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! R...")
- 10:25, 15 February 2023 Distributed Locking Algorithms (hist | edit) [1,654 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Distributed Locking Algorithms (Distributed Locking Algorithms)}} == Description == The purpose of a lock is to ensure that among several nodes that might try to do the same piece of work, only one actually does it (at least only one at a time). That work might be to write some data to a shared storage system, to perform some computation, to call some external API, or suchlike. At a high level, there are two reasons why you might want a lock in a distrib...")
- 10:25, 15 February 2023 Texture Synthesis (hist | edit) [2,195 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Texture Synthesis (Texture Synthesis)}} == Description == Given a texture sample, synthesize a new texture that, when perceived by a human observer, appears to be generated by the same underlying stochastic process. == Parameters == <pre>n: number of pixels</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | tre...")
- 10:25, 15 February 2023 Image Compositing (hist | edit) [538 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Image Compositing (Image Compositing)}} == Description == Image compositing is the act of creating a single image from multiple images. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Petro Vlahos Algorithm || 1985...")
- 10:25, 15 February 2023 InDegree Analysis (hist | edit) [1,166 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:InDegree Analysis (Link Analysis)}} == Description == A simple heuristic that can be viewed as the predecessor of all Link Analysis Ranking algorithms is to rank the pages according to their popularity (also referred to as visibility (Marchiori 1997)). The popularity of a page is measured by the number of pages that link to this page. We refer to this algorithm as the InDegree algorithm, since it ranks pages according to their in-degree in the graph $G$....")
- 10:25, 15 February 2023 All Maximal Non-Branching Paths in a Graph (hist | edit) [1,101 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All Maximal Non-Branching Paths in a Graph (All Maximal Non-Branching Paths in a Graph)}} == Description == A node $v$ in a directed graph $G$ is called a 1-in-1-out node if its indegree and outdegree are both equal to 1, i.e., $in(v) = out(v) = 1$. We can rephrase the definition of a "maximal non-branching path" from the main text as a path whose internal nodes are 1-in-1-out nodes and whose initial and final nodes are not 1-in-1-out nodes. The proble...")
- 10:24, 15 February 2023 Weighted Set-Covering (hist | edit) [2,602 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Weighted Set-Covering (The Set-Covering Problem)}} == Description == The set-covering problem where each set $s\in S$ is assigned a weight and the goal is to find the minimum weight sub-collection of $S$ that covers the universe. == Related Problems == Subproblem: Unweighted Set-Covering == Parameters == <pre>n: number of elements in the universe m: number of sets in the collection d: size of the largest set in collection H(x): the xth Harmonic...")
- 10:24, 15 February 2023 Unweighted Set-Covering (hist | edit) [2,605 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Set-Covering (The Set-Covering Problem)}} == Description == Given a universe $U$, i.e. a set of elements $\{1, 2, \ldots, n\}$, and a collection $S$ of $m$ sets whose union is the universe, identify the smallest sub-collection of $S$ whose union is the universe. == Related Problems == Generalizations: Weighted Set-Covering == Parameters == <pre>U: the universe of elements to be covered S: the collection of sets n: number of elements...")
- 10:24, 15 February 2023 Optimal Policies for MDPs (hist | edit) [1,352 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Optimal Policies for MDPs (Optimal Policies for MDPs)}} == Description == In an MDP, a policy is a choice of what action to choose at each state An Optimal Policy is a policy where you are always choosing the action that maximizes the “return”/”utility” of the current state. The problem here is to find such an optimal policy from a given MDP. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" styl...")
- 10:24, 15 February 2023 Filtering Problem (Stochastic Processes) (hist | edit) [3,213 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Filtering Problem (Stochastic Processes) (Filtering Problem (Stochastic Processes))}} == Description == The filtering problem is to obtain the best linear estimate $\hat{z}_t$ of $z_t$ based on the past observations ($y_s | s\leq t)$. Abstractly, the solution to the problem of filtering corresponds to explicitly computing $\hat{z}_t = P_t^y(z_t)$ where $P_t^y$ is the projection operator onto the Hilbert space $H_t^y$. == Parameters == No parameters...")
- 10:24, 15 February 2023 Culling (hist | edit) [943 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Culling (Culling)}} == Description == Culling is the process of rejecting primitives or objects in their entireity before rendering in the case that they would not be shown in the view, reducing unnecessary computations. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | view fru...")
- 10:24, 15 February 2023 Blob Detection (hist | edit) [2,861 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Blob Detection (Feature Detection)}} == Description == The regions or points which have noticeable difference with their surroundings is called blob. Blob detection is the problem of detecting such blobs in a given image. == Related Problems == Related: Corner Detection == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! App...")
- 10:24, 15 February 2023 Corner Detection (hist | edit) [4,189 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Corner Detection (Feature Detection)}} == Description == Conventionally, a corner is defined as the intersection point or the junction point between two or more straight line edges (i.e. edges which have discontinuities along a straight line). Corner detection is the problem of detecting such corners in a given image. == Related Problems == Related: Blob Detection == Parameters == No parameters found. == Table of Algorithms == {| class="wiki...")
- 10:24, 15 February 2023 Matrix Factorization (hist | edit) [1,316 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix Factorization (Collaborative Filtering)}} == Description == Collaborative filtering is a technique used in recommendation systems. It analyzes relationships between users and interdependencies among products to identify new user-item associations. A method of collaborative filtering uses matrix factorization. In its basic form, matrix factorization characterizes both items and users by vectors of factors inferred from item rating patterns. == Pa...")
- 10:24, 15 February 2023 Maximum Likelihood Methods in Unknown Latent Variables (hist | edit) [3,607 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Likelihood Methods in Unknown Latent Variables (Maximum Likelihood Methods in Unknown Latent Variables)}} == Description == In this problem, the goal is to compute maximum-likelihood estimates when the observations can be viewed as incomplete data. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !!...")
- 10:24, 15 February 2023 Mesh Parameterization (hist | edit) [5,660 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Mesh Parameterization (Mesh Parameterization)}} == Description == Given any two surfaces with similar topology it is possible to compute a one-to-one and onto mapping between them. If one of these surfaces is represented by a triangular mesh, the problem of computing such a mapping is referred to as mesh parameterization. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width=...")
- 10:24, 15 February 2023 Hyperbolic Spline Interpolation (hist | edit) [2,566 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Hyperbolic Spline Interpolation (Hyperbolic Spline Interpolation)}} == Description == The problem of restoring complex curves and surfaces from discrete data so that their shape is preserved is called isogeometric interpolation. A very popular tool for solving this problem are hyperbolic splines in tension, which were introduced in 1966 by Schweikert. These splines have smoothness sufficient for many applications; combined with algorithms for the automat...")
- 10:24, 15 February 2023 Record Matching (hist | edit) [35 bytes] Admin (talk | contribs) (Redirected page to Duplicate Elimination) Tag: New redirect
- 10:24, 15 February 2023 Object Identification (hist | edit) [35 bytes] Admin (talk | contribs) (Redirected page to Duplicate Elimination) Tag: New redirect
- 10:24, 15 February 2023 Instance Identification (hist | edit) [35 bytes] Admin (talk | contribs) (Redirected page to Duplicate Elimination) Tag: New redirect
- 10:24, 15 February 2023 De-Duplication (hist | edit) [35 bytes] Admin (talk | contribs) (Redirected page to Duplicate Elimination) Tag: New redirect
- 10:24, 15 February 2023 Record Linkage (hist | edit) [35 bytes] Admin (talk | contribs) (Redirected page to Duplicate Elimination) Tag: New redirect
- 10:24, 15 February 2023 DAG Realization Problem (hist | edit) [1,159 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:DAG Realization Problem (Graph Realization Problems)}} == Description == Given a sequence $S := (a_1, b_1), \ldots, (a_n, b_n)$ with $a_i, b_i \in \mathbb{Z}_0^+$, does there exist a directed acyclic graph (DAG) (no parallel arcs allowed) with labeled vertex set $V := \{v_1, \ldots , v_n\}$ such that for all $v_i \in V$ indegree and outdegree of $v_i$ match exactly the given numbers $a_i$ and $b_i$, respectively? == Related Problems == Generalizations...")
- 10:24, 15 February 2023 Digraph Realization Problem (hist | edit) [1,531 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Digraph Realization Problem (Graph Realization Problems)}} == Description == Given a sequence $S := (a_1, b_1), \ldots, (a_n, b_n)$ with $a_i, b_i \in \mathbb{Z}_0^+$, does there exist a directed graph (no parallel arcs allowed) with labeled vertex set $V := \{v_1, \ldots , v_n\}$ such that for all $v_i \in V$ indegree and outdegree of $v_i$ match exactly the given numbers $a_i$ and $b_i$, respectively? == Related Problems == Subproblem: DAG Realiza...")