Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
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....
0
votes
0answers
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). ...
0
votes
0answers
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 ...
5
votes
1answer
88 views

discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
2
votes
1answer
34 views

Efficient solution for a particular form of quadratic Diophantine equation

Preface: I know there are a lot of posts already here and elsewhere about algorithms for solving quadratic Diophantine equations in general. I am posting this in the hope that my very particular case ...
1
vote
0answers
35 views

Shortest path as a linear program

I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
2
votes
1answer
54 views

Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?

I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious ...
0
votes
0answers
17 views

Algorithm for optimizing items order with minimum moves [closed]

I have a grid of items on web page with known number of views and clicks (think ecommerce site category page). Click through rate (CTR) of an item is defined as clicks/views. Assume items appearing ...
3
votes
0answers
51 views

Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., $$B := \{(u,...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
33 views

Determine the time complexity of this algoritm (pseudocode)

{ t <- n while t>1 do t <- log_2(t) } I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\...
1
vote
1answer
30 views

Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
2
votes
0answers
42 views

How to impose distance constraint without quadratic constraints?

I have a set of variables $\{x_i\}$ that I want to optimize according to some objective function. However, I would like that $$(x_i-x_j)^2 \geq d^2\ \ \ \mathrm{for\ all}\ \ \ i,j$$ Which is a lower ...
1
vote
0answers
36 views

Set partitioning algorithm that aligns centroids

I have a collection of points $C := \{x_1, \ldots, x_{60 N}\}$ in 3D space. I am looking for a partition of $P$ of $C$ with the following properties: Each of $P$'s sets contains $60$ points, i.e., $P ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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.
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 (...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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'$ ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
7
votes
0answers
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$...
1
vote
1answer
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 ...
0
votes
0answers
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. ...
2
votes
0answers
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 ...
0
votes
0answers
7 views

Looking for algorithm to pack rectangular squares while considering locality

I have a couple of rectangles (~10'000 - 1'000'000) with various integer dimensions where each side is something between 1-10 I got to arrange these (without rotating) into a block of fixed width ...
2
votes
1answer
54 views

Find if two elements in an array sum up to a given number

I'm currently solving some problems over at kattis, in particular the Add 'Em Up task. A quick summarizing: You are given an array with $1 \leq n \leq 100000 $ elements and an integer $2 \leq s \leq ...
2
votes
0answers
25 views

Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
0
votes
1answer
34 views

Search algorithm for an expensive boolean function

I have the following problem. We have a boolean function $f$ that is expensive to compute for a given input. We need to find the smallest positive integer $n$ such that $f(n)$ is true. We don't know ...
1
vote
0answers
26 views

Selecting sets that maximise the cardinality of the union minus the cardinality of the difference

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
3
votes
0answers
11 views

Task scheduling with the constraint of pairs of objects being present in a cache

I'm writing some software that involves processing a large collection of images that are arranged spatially. It basically involves loading pairs of images into caches and computing an operation on the ...
7
votes
1answer
102 views

What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
1
vote
1answer
1k views

Is there a better way to optimize my algorithm for maximizing order volume?

I'm trying to find an efficient algorithm to solve the following ... During the day, a supermarket will receive calls from customers who want to place orders. The supermarket manager knows in advance ...
0
votes
0answers
33 views

Sum optimization and greedy approach

I've came across the optimization bellow $\phi=argmin_{\theta} \displaystyle\sum_{i=1}^{N}f(x_i,\theta)$ Can i say that minimizing this summation by minimizing each term $\left(\displaystyle\frac{df(...

1
2 3 4 5
32