# Questions tagged [optimization]

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

1,254 questions
Filter by
Sorted by
Tagged with
1k views

87 views

### Finding Conflict algorithm doubt

Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time. I have to find an event that conflict with maximum number of other events. Conflicts means interval ...
72 views

### How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or ...
24 views

### Mixed integer non convex optimization problem

If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. ...
44 views

### What algorithm to use for this problem?

I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it ...
58 views

### Pandemic board game - find all possible next 4 actions

I hope I am asking this on the right community. I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and ...
7 views

### In multithreaded computations, how does parallelism, slackness and speedup affect the running time?

In the CLRS book it mentions that during some world-class multithreaded chess-playing program, developers had to prototype their program on a 32-processor computer then run it on a supercomputer with ...
32 views

### Why does such reductions work [duplicate]

In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
45 views

### Optimal flow in a network with non-constant edges' weights

I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
469 views

### Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
23 views

### Rearrange items in order reduce fragmentation and reduce wasted space

I have a segment with some offsets at irregular intervals There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset. Items are free ...
22 views

### Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions: There are "n" jobs which are distributed over the city. Company has "k" available workers. Each worker can do "x" jobs per day. "x" is dependent to the worker skills and the distance ...
44 views

### Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
14 views

### Performant algorithm to find edges without cross overs

I have a series of graphs with points plotted like this: Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don'...
35 views

### Weighted Activity Selection Problem with allowing shifting starting time

I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists. In my case, I am allowed to ...
13 views

### Can one pose an optimization problem as a problem in machine learning?

There seems to be an increasing trend towards posing problems in the realms of classical optimization theory as machine learning problems. Can you explain when one would resort to using machine ...
19 views

### Dynamic programming algorithm with an O(n) performance that will give the optimal solution

I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming ...
20 views

### Is there a way to *round* a nearby point into the feasible set?

Let $P \subset \mathbb R^d$ be a polytope with interior given by $F$-many linear inequalities. Suppose we have a convex problem with feasible set $P$. For example computing the Euclidean projection of ...
33 views

### How Expensive is Projecting onto a Polytope?

I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
21 views

### is the complexity of an algorithm connected to the “classification” of a optimization problem?

I wonder if the complexity is connected to an optimization problem. In general but also specifically e.g. when having a look at $O(n^2)$. Does this just describe the complexity in general or does it ...
25 views

### Solving the 0-1 Multiple knapsack problem via Dynamic programming?

I want to code a variant of 0-1 Multiple knapsack problem via Dynamic programming. Problem: Given a set of n items and a set of m bags (m <= n), with ...
40 views

### Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
63 views

### How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?

Here is the problem: Input: A series of source/sink nodes at fixed positions with given outwards/inwards flow Edges are NOT specified. The edges can connect any nodes. The total source and sink ...
90 views

### Finding bounded lexicographically largest string of digits but not larger than other with counted substitutions

The problem comes from the book текстовые и жадные алгоритмы (String and greedy algorithms) by a fairly unknown Russian computer scientist Николай Сухоруков. We are given two numbers $A$ and $B$ of ...
26 views

### Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
22 views

### Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
2k views

### Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
27 views

### Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the ...
37 views

### Is unconstrained quadratic programming NP-hard?

I could not find the answer on the Internet. The case of quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But ...