# Questions tagged [optimization]

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

1,361 questions
Filter by
Sorted by
Tagged with
49 views

### Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

Let $A$ be a an $n\times m$ real valued matrix. The problem is to find the minimal subset $I$ of rows (if there is any) such that the sum of each column $j$ over the corresponding rows exceeds some ...
18 views

### How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
10k views

### Why do we need full-fledged workstations running massive OSes with massive software?

I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of ...
924 views

### Optimal meeting point

I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point ...
1k views

### Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
28 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 ...
37 views

### Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
1k views

27 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)$. ...
57 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 ...
223 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 ...
17 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 ...
33 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 ...
50 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 ...
595 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 ...
26 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 ...
16 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'...
39 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 ...
17 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 ...
25 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 ...
39 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 ...
76 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 ...
47 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 ...
79 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 ...
96 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 ...
75 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 ...
27 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 ...
42 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 ...
104 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 ...
56 views