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
2answers
939 views

Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...
4
votes
1answer
305 views

An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given. For example ...
-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
votes
0answers
33 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
0answers
13 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 ...
3
votes
1answer
182 views

Image registration using gradient descent

I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$ I want to align $g$ to $f$ using the transformation : $$\Psi(x,y;t_x, t_y, \theta) = \begin{...
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 ...
3
votes
1answer
79 views

Improve algorithmic complexity

We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do: ...
2
votes
1answer
39 views

Optimal Selection of Non-Overlapping Jobs

I'm trying to find what the family of problem is - as well as an approach - for the following: I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task ...
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 ...
0
votes
1answer
253 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
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+...
3
votes
0answers
165 views

How to compute an optimally cost-effective cache strategy?

I am looking for advice in the following optimization problem. I have a website (system) that receives database updates. The updated information is later returned in queries made to the same system. ...
0
votes
1answer
29 views

Is this a good way of generating diverse solutions to a problem using a genetic algorithm?

Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values ...
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 ...
4
votes
0answers
35 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 ...
4
votes
4answers
995 views

Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an ...
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, ...
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,...
9
votes
2answers
244 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their stable, ...
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
135 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 ...
1
vote
1answer
19 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
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}...
0
votes
3answers
118 views

What is the best hash functions for millions of String keys?

I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value. The problem that the retrieval process is too slow and I want to ...
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
1answer
44 views

simple question about epsilon and estimation turing machines

i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
2
votes
1answer
88 views

Encoding set of At-Most-One constraints as a MAX-SAT problem

Assume a set of variable $V$ = $\{v_1,...,v_m\}$. Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$, $$ AMO \...
1
vote
1answer
64 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
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

How to do supervised learning without knowing the target

I'm working on an optimization algorithm that I think could be considered machine learning, but I'm not sure. Basically I have a model that I want to optimize by adjusting its parameters. I don't ...
4
votes
1answer
122 views

Inexact cover, or cover with gaps

Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem. In the Knuth's research papaer, linked above it is shown how Polymino problem (that is ...
0
votes
1answer
83 views

Integer Linear programming formulation if then condition

I want to create constraints such that I can implement the following condition: Let A be an integer variable >= 0 with an upper bound of 12 I want to introduce the following variable B also an ...
2
votes
2answers
444 views

Are most metaheuristic algorithms different metaphors for the same method?

Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to ...
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 ...
1
vote
1answer
52 views

Method for combining derivative free optimization results of different data inputs

I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as ...
0
votes
1answer
28 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 ...
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
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 ...
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 ...
1
vote
1answer
136 views

How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$?

How can TSP be an NP-optimization problem ? The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and ...
2
votes
1answer
396 views

Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in ...
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 ...
2
votes
1answer
94 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
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
71 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
17 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 (...

1
2 3 4 5
30