Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [optimization]

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

136 questions
Filter by
Sorted by
Tagged with
4k views

### How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That ...
4k views

### How to identify when to use Genetic Algorithm/Programming

I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem. TSP is basically a permutation/combination problem, and I can understand how GA helps ...
780 views

### Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
8k views

For my case I have starting point and several cities. I want the shortest route to visit all cities without returning starting point. I have read several TSP algorithm and all include the return a ...
530 views

### Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
2k views

### Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
775 views

### Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map): positively weighted undirected sparse with about 100 nodes My ...
1k views

### Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
200 views

### Which potential function does this algorithm minimize or maximize?

Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^S = \min_{x' \in S \setminus \{x\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$ denote the Euclidean ...
104 views

### Location Selection Algorithm in Solar Engineering

This is a practical problem in energy generation with heliostats. We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One ...
527 views

### Is this problem NP-hard?

Good day. Subset sum selection problem is NP-hard. I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of ...
4k views

### Assignment based on ranked preference

Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the <...
1 vote
2k views

### Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
1 vote
207 views

### Literature on network-flow (optimization) approximation algorithms

I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree. However, I have been looking in several well-known ...
65 views

### Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP ...
207 views

### Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
1k views

### Knapsack with same value

I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight ...
803 views

### What is the optimal way to cut B chocolate bars to share equally between N people?

What is the optimal way to cut B chocolate bars to share equally between N people? Here is an example of different cuts for B = 5 chocolate bars and N = 6 people. Strategy 1: cut each chocolate bar ...
2k views

3k views

3k views

### Knight on a chessboard

This is a Hackerrank challenge $Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ ...
We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...