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
1
vote
0answers
64 views

Difference between Memetic and Cultural algorithms

What is the difference between a memetic algorithm and a cultural algorithm? I mean they're both evolutionary algorithms where they select a subset of the population to apply some local search logic. ...
2
votes
0answers
220 views

Geometric interpretations of midpoint algorithm, homogeneous linear least squares and nonlinear least squares method in 3D reconstruction?

In "Multiple View Geometry in Computer Vision" Chapter 12. Structure Computation, page 310-313, triangulation is used for point 3D reconstruction. There are three methods mentioned: Midpoint method ...
1
vote
2answers
190 views

What is the name for polynomially solvable optimisation problems?

An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known. Symmetrically, ...
5
votes
1answer
255 views

Maximize product of sum of two subset

Given two sets $A = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$, both consist of positive numbers, this problem is to find a subset $S$ in $\{1, 2, \dots, n\}$ to maximize $$ \left(\...
3
votes
4answers
176 views

Optimization problem where penalty is sensitive to permutation

Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I ...
1
vote
0answers
22 views

optimization problem: Find Phase of input for minimized max output [closed]

Let the $\textbf{bold characters}$ represent the vectors/matrices.All the vectors/matrices/scalars only refer to real numbers. In a continuous LTI system. $\frac{d\mathbf{T}(t)}{dt}=\mathbf{A}\...
4
votes
0answers
128 views

Sequence Alignment with Skips

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
7
votes
1answer
3k views

BFGS vs L-BFGS — how different are they really?

I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum ...
0
votes
1answer
124 views

How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started ...
0
votes
2answers
171 views

Design Hashing function from known distribution of bits to be set

How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash ...
2
votes
2answers
631 views

Worst case using the first fit $2$-approximation for the bin packing problem

I am with the phone so I would be more verbose when I will have a pc on hand, if you desire. The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the ...
5
votes
1answer
1k views

How can I restructure matrices to have non-zero elements close to the diagonal?

I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members ...
-1
votes
2answers
149 views

Algorithm to allocate resources to minimize the maximum of any party

I was given the following algorithms problem: Suppose you have $n$ cities. Each city $c_i$ has population $p_i$. You want to construct $m \geq n$ schools, where each school can only serve ...
0
votes
1answer
54 views

Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)

There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of # operations. When I do ...
2
votes
0answers
64 views

Finding the smallest tree of given weight

Take a node-weighted, undirected graph $G$, and a node $r$ in $G$. Is there an efficient algorithm to find a tree in $G$ rooted at $r$ which has total weight at least $w$ and contains a minimal number ...
2
votes
1answer
222 views

Minimizing transportation cost through a network, multiple source/sinks

I have the following problem: Inputs: A finite collection $V$ of vertices A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$) An amount of ...
0
votes
1answer
38 views

Optimizing estimator of composed functions when function is known

I have a problem which I'm looking to see if there is literature on: Consider three types of actors, a Director, Aggregator, and Follower. The Director talks to multiple Aggregators, the Aggregator ...
4
votes
0answers
214 views

Graph optimization problem with multiple objectives/constraints

Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We want to divide ...
3
votes
1answer
176 views

Solving for the minimum cost, colored, set cover

Formulation This problem has four entities: A universe: $U = \{1, 2, ..., n\} $ of $n$ elements, indexed with $u$ A set of available colors: $C \in \{1, 2, ..., m\} $ with $m$ colors, indexed with $...
5
votes
0answers
422 views

How to apply ant colony optimization to the TSP but repeating nodes and edges

I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
0
votes
1answer
170 views

Breaking down CNF clauses

I have an assignment where i have to encode certain problem to conjunctive normal form so i can solve it by using SAT solver. I have been able to encode my problem correctly but the solver is quite ...
1
vote
3answers
413 views

Match dictionary to misspelled word, corner cases

I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word w1, find all matches with the least editing distance from it in the ...
4
votes
2answers
130 views

Discrete assignment problem with penalties

I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods. It's an single agent problem where we have to ...
5
votes
1answer
260 views

Can I prove that I have x such that f(x) < c without revealing x?

I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob ...
2
votes
1answer
267 views

Approaches to the size constrained weighted set cover problem

I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended ...
1
vote
0answers
158 views

State-of-the-Art techniques on dynamic shortest path computations

Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
0
votes
1answer
19 views

Optimizing cheap functions on mixed search space

Assume we have a really cheap function $f$ that is defined on a mixed parameter space and we want to find a minimum. For example $\operatorname{arg\,min}\limits_{x_1,x_2,x_3} f(x_1,x_2,x_3)$ with $...
1
vote
0answers
48 views

Update existing clusters to satisfy distance and volume constraints

I have a massive distance matrix of clusters. The distance matrix is the distance between each cluster. I now need to recluster each entity based on two constraints. Each cluster has an associated ...
1
vote
1answer
49 views

Find K-subset that includes the most W-subsets

I have a set $S$ of $N$ elements, and a set $\Sigma$ of $N$ subsets of $S$: $\sigma_0, \ldots, \sigma_{N - 1} \subset S$, each with $W \ll N$ elements. Subsets can overlap partially or totally. For ...
13
votes
2answers
606 views

Matrix chain multiplication and exponentiation

If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}...
-1
votes
1answer
559 views

Best way to schedule jobs so as to get minimum average turnaround time [closed]

The question is right there above.
2
votes
1answer
99 views

Direct encoding of the solution into the chromosomes in a Random-Key Genetic Algorithm

In a random key genetic algorithm1, the chromosomes consist in a sequence of real numbers (initially randomly generated) in the interval $[0,1]$. I've been told by my teacher that in these kinds of ...
0
votes
2answers
965 views

Reducing time complexity for finding all possible triplets in an array? [closed]

So I have an array sized N. It is sure that array has all distinct elements. I need to find sum of all possible triplets in that array and for that i need to find all possible triplets. What i did: ...
4
votes
1answer
353 views

Vehicle Routing Problem with multiple deliveries?

I have a problem that can be reduced to the following: There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points"...
0
votes
0answers
541 views

Maximum Subarray Problem Algorithm that uses divide and conquer but runs in linear time

I am trying to design an algorithm that computes the largest (by sum) contiguous subarray of an array of size n that uses a divide and conquer approach, but runs in linear time. The standard divide ...
2
votes
0answers
35 views

is mappings optimization problems onto neural networks still a thing?

Is mappings optimization problems onto neural networks still a thing? I only found papers are written prior to 1999. These old papers mostly deal with Hopfield network, which i read is obsolete and ...
2
votes
1answer
518 views

Maximum weight sum in a subgraph

Let $G = (V, E, W)$ be a weighted graph with positive and negative weights. I would like to find the set of vertices $V^\prime$ such that the sum of the weights of the edges that they share is the ...
0
votes
1answer
57 views

How can i fill shelves with products so that I have the maximum amount of sales?

I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales ...
3
votes
2answers
1k views

Hamiltonian path in grid graph

Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that ...
2
votes
1answer
275 views

decision tree redundancy optimization

First question in the computer science section. I am currently working on a solution that optimizes decision tree redundancy. the following is an example of optimization: ...
2
votes
1answer
135 views

Do not understand a lemma regarding dinics algorithm

Here you can find the following lemma with its proof. Lemma: In a network with unit edge capacities, Dinitz algorithm terminates after $O(\sqrt{m})$ blocking flow computations. Proof: Consider the ...
2
votes
1answer
103 views

Online algorithms and changing past decisions

We know that for some online problems, algorithms can decrease their competitive ratio greatly if they are allowed to change some of their past decisions (see http://epubs.siam.org/doi/pdf/10.1137/1....
0
votes
2answers
366 views

It's necessary to replace all the population each generation in a genetic algorithm?

I'm creating a timetable generator using GA's, and I'm stuck in the crossover part. Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), ...
5
votes
0answers
41 views

Cuttings sticks in congruent equal sharing

You have $n$ congruent sticks (they have the same length). You want to divide them equaly among $m$ friends. To avoid envy, each friend should receive congruent parts, that is, the set of cutted ...
1
vote
1answer
236 views

Find most valuable subset of a node weighed tree

Suppose you got a directed acyclic graph of positvely and negatively weighed nodes $T\hspace{-0.02 in}$. Now I have to find the the subset ​ $M\subseteq T$ ​ such that the sum of the weights of the ...
2
votes
3answers
127 views

Why computer take long time to open huge text files? [closed]

Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be ...
3
votes
1answer
58 views

Difference between large-scale optimization and equation-based simulation

Large scale optimization (for example using AMPL) can be used to solve equilibrium systems which have components with fixed mathematical relationships. What is the difference between this and using an ...
0
votes
0answers
212 views

Seating-Chart Optimization

Does anyone have any ideas on a seating chart optimization formula for a call center environment? There are "docks" in which the workers sit. Each dock has approximately 15 seats, some more some less. ...
3
votes
0answers
424 views

Optimal pairing of points in a set

I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the ...