A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [optimization]

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

1,269 questions
Filter by
Sorted by
Tagged with
71 views

### Polynomial LP-based algorithm for cost minimization of DAG weights modification

Given a DAG $G=(V,E)$, with non-negative weights $w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that: $\forall u,v\in V$ and $\forall p_1\neq p_2$ paths from $u$ to ...
1k views

### Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once? I'd like to know if there is a general approach to this ...
797 views

### Modification of Dijkstra's algorithm

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality? There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
361 views

281 views

### There are n numbers. Find the maximal set of pairwise NON coprime numbers

I have to take input in an array(no. of elements in array <=10^5). For ex:- Let the array be {2,3,4,16,9,45,81,27} Now I need to find the order of the maximal set such that any pair of elements in ...
116 views

### Performance gain by implementing streamlined simplex

I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of ...
155 views

79 views

### Is my implementation of genetic algorithm correct?

In genetic algorithms, we have a function called "mutation". Before we call this function, we choose parents. In my version of the algorithm, when i mutate the child, i don't change the bits which ...
2k views

### How can I generate Rubik's cube algorithms equivalent to a given algorithm?

I am developing a computer program that solves the Rubik's cube. It is not anything advanced nor fast. It solves the cube by the Friedrich method, using algorithms that I use in real life to solve the ...
519 views

### Understanding the bandwidth problem on graphs

I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list: ...
183 views

### Is there a name for the knapsack problem with no bound on knapsack capacity?

I am investigating heuristics for optimising the packing a fixed number of knapsacks with a set of items of defined weights, however the knapsacks do not have a defined capacity limit. The objective ...
310 views

79 views

### Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language): ...
3k views

### Dynamic Programming vs Greedy - coin change problem

This is a fairly common problem: Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible. Given an input of powers of $p$, ...
116 views

### Algorithm: How many symbols of occurence k fit into b buckets under condition

I have the following problem to solve: Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size. Place ...
134 views

### A specific version of a job scheduling problem

I'm looking for a solutions or book references to a given variation of a job scheduling problem: Given $n$ machines (let's denote it by $m_1, m_2, \ldots, m_n$) and $r$ tasks ($t_1, t_2, \ldots, t_r$)...
366 views

### Using AI / Machine learning to find the most time and space efficient solutions to an algorithm [duplicate]

As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms. Is it forseeable in the future that we have languages or techniques such as AI/...
159 views

### Making mathematical expressions as balanced trees as possible

I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible. This is what I have done so far, but is there a way to make them even more ...
130 views

### FPTAS, except not polynomial in size: which class?

Problems in FPTAS require time which is (at most) polynomial in problem size. Suppose this last requirement is relaxed. What is the corresponding approximability class and where can one read about it? ...
327 views

### An algorithm to find the maximum profitable assignment

Given a set of workers $w_1,...,w_m$ and and a set of tasks $t_1,...,t_n$, and a $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be ...
881 views

### Anyone knows an algorithm that finds minimum distance for all permutations?

Let $A$ and $B$ be two finite sets of the same size $n$. Let $P(A),P(B)$ be the set of all permutations of $A,B$ respectively. A distance function $d(a,b)$ is defined for any $a\in P(A),b\in P(B)$. We ...
4k views

### Single-Source Shortest Path with at most k edges using Dijkstra's algorithm

I am trying to solve a bounded SSSP problem as follows: Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with ...
The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$: $max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}$ subject to $\displaystyle\sum_{i} w_ix_i \leq W$ for a ...