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
-3
votes
0answers
15 views

Reordering an array to maximize expression

You are given 2 arrays $a$ and $b$ of size $n$. Your task is to reorder array $b$ such that the following expression is maximized. $$(a_1\ ⊕\ b_1) \& (a_2\ ⊕\ b_2)\& (a_3\ ⊕\ b_3)\& \ ... \...
1
vote
0answers
14 views

How to calculate image gradient with respect to homogeneous coordinate vector?

I want to use the direct method of computing the homography between two images to estimate the plane parameters (normal and depth [= distance from camera]) of a 3D plane. If we have two images of the ...
1
vote
0answers
30 views

Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
1
vote
1answer
49 views

Variant of assignment problem

This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
1
vote
1answer
48 views

solve a rational equation as fast as possible

I would like to find the first positive solution(if there is one) to this equation: $$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$ The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+...
0
votes
0answers
25 views

Coordinate descent for Lasso, Question about algorithm

I'm not sure why the algorithm computes $c_k$ with $\sum_{j \neq k} w_j x_{i, j}$. Why does one need to ignore the $k^{th}$ feature here? I'm not sure how this is derived. Is this the result of taking ...
1
vote
0answers
10 views

How are randomized restarts in local search 4 times likely to give bad local minima?

I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They, ...
4
votes
0answers
36 views

2-Dimensional interval scheduling problem

I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format: Cars with the start and ...
1
vote
0answers
44 views

0/1 Knapsack problem with minimal cost

so i have this problem where: I have to accomplish a challenge A with n quests. Each quest gives me: p points and needs t time to be done. The object is to complete the challenge A that needs M ...
1
vote
1answer
20 views

Online approximation algorithm for median?

Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$? The scenario is: I have a ...
0
votes
1answer
40 views

Exit quickly from a maze with a local view of the maz

How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)? you don't know the maze configuration but you know where your player is, and which ...
-1
votes
0answers
34 views

Minimally changing string to make it palindromic

Given a string STR of size $N$ and some queries $Q$, find for each query the minimal number of characters which when changed makes that substring a palindrome. For example: $\mathrm{STR} = aabbdca$. ...
1
vote
1answer
36 views

Is the Jacobian matrix calculation process correctly on this energy function?

When I implemented the paper Dynamic Fusion published in 2015 CVPR, I came into the trouble with how to solve the energy function: $$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t) + λ\text{Reg}...
2
votes
1answer
12 views

Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...
0
votes
0answers
10 views

How to use XML format of graphs in Graph neural network?

I have manually labeled directed graphs that I need a GNN to train on and then predict when given a new directed graph, what the labels for the vertexes in the graph should be. My graphs are in the ...
1
vote
1answer
65 views

Can someone help me understand the time and space complexity?

Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the ...
0
votes
0answers
27 views

Trying to design an algorithm for finding a number in a range

I'm trying to design an algorithm that finds a number in a given range. The only signal we get for a given guess is: "Is our guess less than the magic number?" I'm trying to: Optimize the ...
0
votes
0answers
14 views

Min number of register without spilling

The program below uses six temporary variables a, b, c, d, e, f. a = 1 b = 10 c = 20 d = a+b e = c+d f = c+e b = c+e e = b+f d = 5+e return d+f Assuming that all ...
0
votes
1answer
29 views

Probability of Attaining the/a Global Optimum

Suppose for a given optimization problem, $A$, the size of the search space $S$ is |$S$|. If the fitness landscape defined by $A$ is unimodal, then there is clearly only one global optimum. Given that ...
2
votes
1answer
106 views

Efficient algorithm to compute the diameter of a convex set?

Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set? It is possible to do it efficiently for a set of points, but imagine that the ...
0
votes
1answer
26 views

SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$?

I am trying to understand SVMs in depth watching lectures from MIT. The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and ...
0
votes
1answer
45 views

How do I assign homes to hospitals based on locality? (clustering, kmeans?)

I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,...
2
votes
1answer
23 views

Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?

How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me ...
1
vote
0answers
15 views

Measure divergence in Particle Swarm Optimization

I'd like to monitor divergence/diversity in my swarm during the particle swarm optimization algorithm to measure when the swarm search space is converging. This would be used as one metric to be ...
4
votes
1answer
68 views

Bin packing when items can be broken

In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break ...
1
vote
1answer
30 views

Must an optimization problem with a greedy algorithm belong to P?

If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
1
vote
1answer
75 views

Partitioning list into two parts of almost equal sum

I was given this problem in class, and I have no idea how to solve it. The problem is: "Given a list of positive integers, divide the numbers into 2 groups such that the difference between the ...
1
vote
0answers
18 views

Equally optimal nodes during minimax with alpha-beta pruning

Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (...
0
votes
0answers
34 views

Computing a fractional matching of maximum product in a bipartite graph

Given a bipartite graph $(X\cup Y, E)$ with edge weights, it is easy to find a matching in which the product of weights is maximum: replace each edge weight with its logarithm, and find a matching in ...
1
vote
1answer
62 views

Which data structure can be used to determine most experienced person in a shift?

Problem Statement: There are $n$ hours in a day and you have $w$ workers. For each worker $i$ you will be given $x_i$ (work experience), $s_i$ (shift start time) and $e_i$ (shift end time) on a ...
3
votes
1answer
140 views

Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$

I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
1
vote
0answers
12 views

What is spatial information in neural network? [duplicate]

The architecture of the CNN model contains several convolutional layers, non-linear activations, batch normalization, and pooling layers. The initial layers learn the low-level concepts such as edges ...
1
vote
0answers
15 views

What problem is this application of simulated annealing trying to solve?

I was reading about simulated annealing on its Wikipedia page, and was drawn to a particular example illustrating the annealing schedule. Below is the picture and its description: Example ...
1
vote
0answers
18 views

Complexity of solving fractional constrained set multicover

Recently, I've encountered the following problem: Given a collection of sets $S_1 \dots S_n$ of elements $e_1 \dots e_k$ with element $e_k$ denoted privileged, and a $k-1$-vector $r$, choose at most $...
1
vote
1answer
50 views

How to remove an ordering requirement from a board game simulation?

The Problem: I'm trying to simulate part of the game tantrix which is a board game played with hexagonal tiles. Each tile has 3 lines of different colors that each start at one side of the hexagon ...
1
vote
1answer
31 views

Maximum-coverage minimum-overlap intersection of sets

I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for. The ...
0
votes
0answers
18 views

What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
1
vote
2answers
59 views

Best approach to resource allocation problem

Problem The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
1
vote
1answer
23 views

Is transfer learning applied on only similar datasets only?

I am trying to make a CNN model on different brands of logos . Firstly , I wrote a CNN from scratch and trained it on which I got 70% accuracy, I have total 40 classes and each class has 100 images . ...
1
vote
1answer
50 views

What is the Number of epochs with no improvement after which training will be stopped.?

I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check ...
2
votes
1answer
52 views

Optimization problem over bidirectional connected graph

A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
0
votes
0answers
14 views

How do I choose the right model for production?

I am trying to build a classification algorithm having 28 classes. These classes consists of Logo of companies like adidas , Nike etc. I have very low dataset below than 100 images and greater than 70 ...
1
vote
0answers
33 views

Given consumer grade hardware,what is a reasonable upper bound for size of search space?

There's a gacha RPG I'm trying to get better at. I estimate there are about 10^15 states for the 3 opening rounds of a match for which I am trying to evaluate damage output. The equations themselves ...
4
votes
1answer
55 views

Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane. the polygons are either convex or star-shaped with a ...
2
votes
2answers
83 views

Maximize number of subsets

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $...
1
vote
1answer
24 views

Finding optimal separating value

Problem description We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
0
votes
0answers
39 views

A multidimensional “moving van problem”: a mix of a knapsack and a bin-packing problem

This problem is a mix of the bin-packing and the knapsack problems. I call it "the moving van problem": there is a moving van with a limit on the weight it can transport, and a set of boxes ...
2
votes
1answer
32 views

Compute several histograms with multiple filter conditions

I have a numerical dataset of $N$ columns ($\approx 150$) and $K$ rows ($\approx 60000$). On a user interface, you can apply a filter to one or more columns. We can call the number of filters = $Z$ (...
2
votes
1answer
43 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
0
votes
1answer
32 views

Area preserving distance optimization

I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find ...

1
2 3 4 5
30