# Questions tagged [optimization]

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

1,572 questions
Filter by
Sorted by
Tagged with
31 views

### Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
18 views

### Assignment Problem when Edges are Dependent on Other Edges

I have a problem I'm trying to solve: I have 48 individuals which all have some skill, s. I want to assign these individuals into teams of 3 individuals such that the team skill is S, (s1 + s2 + s3). ...
11 views

### Arranging rectangular textures in square texture atlas and optimize sub texture proximity

I have a mesh consisting of about 100'000 - 200'000 quads. Each quad has a rectangular texture. I'm packing these rectangular textures into a power-of-two atlas. My packing algorithm currently works ...
88 views

14 views

### Efficient intersection detection between disks with identical radius

I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose ...
27 views

### Minimize waste for wood router machine

I am not sure if this is the right place to ask this question but of all StackExchange communities, this looks to be the closest one. We have to cut an equal number of circles of 5 different diameters ...
56 views

### Cover 2 by n binary matrix with submatrices of minimum total size

This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
63 views

### How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
24 views

### Is there a concept in computer science where you wait to allocate resources to a more important process?

Let's say you have a limited resource of 5 things. A bunch of unimportant resource acquires want those 5 things. You want to wait for the important resource acquirer to come along and obtain one of ...
22 views

### Fitness Functions, Landscapes and Basins of Attraction

In optimization, particularly evolutionary computation, we often try to optimize (through either minimization or maximization) non-smooth, non-differentiable, discrete functions that aren't readily ...
115 views

### LQR optimal control of accumulator via dynamic programming

Let $$x_{k+1} = x_k + u_k, \qquad x_0 = 5$$ where $k \in \{ 0,1,2,3 \}$, define the return function $$- \sum_{k=0}^3 \left( x_k^2 + u_k^2 \right)$$ with the following inequality constraints on the ...
13 views

### Same instances for different problems

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?). So, two problems may ...
33 views

32 views

### how do i formulate this assignment optimisation problem?

Individual i, associated with organization k, are to be deployed at facility j. Each individual has a cost cij of being deployed at j, and each facility has a minimum number of men required bj. In ...
393 views

### Minimize the expected value of money spent on boxes until the prize is found

There are $n$ closed boxes and one and only one box of them contains a prize. The $i$-th box has probability $p_i$ of containing a prize. A player must pay $c_i$ coins to open the $i$-th box. The ...
14 views

### How to write code for levy flight in cuckoo search

I want to write levy flight random number distribution code for cuckoo search optimization. So how to select randomly two instances from set of instances by levy flight.
27 views

### How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
16 views

### the convergence of the iterative algorithm has a major problem

In order to solve an optimization problem, I divided the main problem into two sub-problems. The two sub-problems require to be solved iteratively until the algorithm converges. I use the bi-section ...
50 views

### Finding the Solution out of N possibilities

Suppose there are 10 (4x4) matrices, where the elements in each matrix are dependent on one variable ($\theta$) non-linearly. All the matrices are independent of each other, so there are 10 $\theta$s (...
21 views

### Software/library to generate Ising models for random $k$-sat problems

Could someone point me to a software/library which lets one to generate the Ising model/spin model for random $k$-sat problems or $k$-sat problem of a given structure? I understand that it will be ...
31 views

### How to choose the initial temperature in the Boltzmann selection method?

Using the Boltzmann selection in genetic algorithms, the probability of visiting a point in optimization space $X_j$ is $p(X_j)=\frac{\exp\frac{-f(X_j)}{T}}{\sum_i \exp \frac{-f(X_i)}{T}}$ my question ...
25 views

### Minimum spanning tree where weights of edges are intersecting sets

Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S_e \ \forall e \in E$. Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ ...
32 views

### Simple efficient algorithm for dynamically maintaining max of special linear functions

Given $n$ tuples $(k_i >0,a_i >0)$, is there any efficient algorithm that can dynamically track $$\max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\}$$ in response to ...
32 views

### NP-hardness proof of an optimization problem with real values and real input in the decision problem

Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
34 views

### Approximation classes for optimization problems with real values

Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.? If my understanding is correct a ...
82 views

### NP-hardness proof of an optimization problem with real values and rational input in the decision problem

I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated. For the question, take the ...
59 views

### What makes Deep RL "fundamentally/mathematically" advantageous?

Note: I consider myself to be a beginner in the field of Deep RL. Deep RL has proven tremendous success in recent years like playing atari and beating go champion. Therefore, considerable interest for ...
6 views

### Are goal-reaching and optimizing the utility function special cases of performance measure?

In َArtificial Intelligence: A Modern Approach by Russell, performance measure is defined as something evaluating the behavior of the agent in an environment. Rational agents are defined as agents ...
18 views

### How to mix populations in multi population genetic algorithm?

I'm working on an optimization problem using genetic algorithm. To increase diversity of potential solutions I'm using multi-population approach: Instead of evolving one population I run 10 ...
151 views

### Finding a rainbow independent set in a circle

Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
155 views

### Minimum Cost Arrangement

I want to find an arrangement to evenly place 12 items ($a_1, a_2, ..., a_{12}$) into 4 boxes ($b_1, b_2, b_3, b_4$) such that the cost is minimal. Let $b(x)$ be the index of the box that contains ...
19 views

### Score and bound in Goemans-Williamson algorithm

I am trying to have a deeper understanding of the following implementation of the Goemans-Williamson algorithm for solving the maxcut problem. ...
17 views

### Algorithm to batch individual cells into blocks based on attribute

This is a real world algorithms problem I came across while coding an application for excel. The background: In excel, we have to write color information to the sheet one cell at a time - there are no ...