# Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

130 questions
Filter by
Sorted by
Tagged with
10k views

7k views

### The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
2k views

### How do quantum computers find the global minimum?

If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, ...
7k views

### How to find spanning tree of a graph that minimizes the maximum edge weight?

Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
2k views

### Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
1k views

4k views

### Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
2k views

### Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...