# Questions tagged [optimization]

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

1,271 questions
Filter by
Sorted by
Tagged with
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. ...
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 ...
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, ...
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(\...
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 ...
22 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
19 views

559 views

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

The question is right there above.
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 ...
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: ...
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"...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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....
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), ...
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 ...
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 ...
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 ...
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 ...
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 ...