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

learn more… | top users | synonyms

2
votes
2answers
67 views

Interpolation Optimization Problem

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - M by N Matrix). Someone marks some pixels as anchors. Now, you need to ...
1
vote
0answers
27 views

Gradient descent vs. Newton's method: which is more efficient?

Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both ...
1
vote
1answer
51 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality [closed]

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
5
votes
1answer
45 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 ...
8
votes
6answers
1k views

How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best ...
2
votes
1answer
53 views

How to optimally seperate a student body?

Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with ...
1
vote
1answer
66 views

Traveling Salesman: how to use a lower bound?

Let me preface this question by giving some helpful background material. I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the ...
5
votes
2answers
92 views

Unknown notation “$e^T$” in a machine learning paper

I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained ...
1
vote
1answer
58 views

Automatic seat assignment algorithm [closed]

I am looking for articles relating to algorithms that deal with automatic selection of seating assignment. I need an algorithm (preferably more than one) that can automatically select a seating place ...
0
votes
0answers
15 views

In multi criteria decision making, what notions are there to get a subset of the Pareto set?

In the multi criteria decision making context, let $\mathcal{A}$ be a set of alternatives or choices. Each alternative $\alpha\in \mathcal{A}$ is a vector of $k$ criteria $\alpha=(v_1,v_2,\dots,v_k)$. ...
2
votes
0answers
73 views

Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
1
vote
0answers
28 views

Practical Application of Kadane algorithm

Kadane Algorithm is used to solve the maximum subarray problem which in simpler terms is to find the highest possible value of a continuous sub array in an array. One often cited application of ...
1
vote
0answers
22 views

Assigning packages to different points by minimizing distance: is this a known problem?

Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of ...
3
votes
1answer
41 views

Choosing a subset to maximize the minimum distance between points

I have a set of points $C$, and I have the distance between each point $D(P_i,P_j)$. These distances are euclidean but the points are actually in a feature space. From the $C$ points I want to choose ...
1
vote
0answers
25 views

Mutation and crossover operations in discrete differential evolutionary operations?

I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of ...
-4
votes
1answer
9 views

Is this problem a multi-objective optimisation problem? [closed]

Efficiency must be maximised and accuracy must be at least 97% for a algorithm doing image recognition in a database. In question (as stated in the question) is the dimension of the objectivness, ...
0
votes
1answer
42 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the ...
3
votes
2answers
154 views

Suboptimal Solution for a combinatorial problem

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is ...
0
votes
5answers
101 views

What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer). What is the best way to ...
2
votes
0answers
33 views

Boat riddle as a Combinatorial optimization problem?

Hello I study computer science and I just digged into combinatorial optimization and ILP. I remember a riddle abotu a bunch of people on a river bank, and a boat with limited capacity (lets say the ...
2
votes
1answer
94 views

Bin packing problem or not?

Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items): Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to ...
6
votes
0answers
29 views

Boolean formula that agrees with most truth assignments

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to ...
0
votes
0answers
27 views

Balanced partition problem for N =< 60 and very large sums

I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S*N) cant run under ...
3
votes
2answers
84 views

minimizing the summed cardinality of set unions

this optimization problem, I am working on, is kind of making me crazy. ;) Given is a list o of sets (with finite cardinality) of strictly positive integer values ...
2
votes
1answer
67 views

How to stop genetic algorithm population converging to a single value

I've written a genetic algorithm (GA) that solves a 7-dimensional optimisation problem. All seven variables are floating point numbers. The problem is that the entire population seems to converge to ...
0
votes
0answers
26 views

Does using diploid (dominant/recessive) genes in genetic algorithm offer any advantage? [duplicate]

I've been looking into diploid genetic algorithms for a while. Although, it seems like an implementation which includes diploid (dominant/recessive) genes is closer to the implementation that has ...
2
votes
1answer
47 views

Genetic algorithm fitness function [closed]

I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function. ...
2
votes
1answer
84 views

How can we minimize the total distance of cross pairs in an array

Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized. The first thought ...
4
votes
2answers
456 views

What is the no free lunch theorem?

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser ...
3
votes
1answer
61 views

Finding largest subset that matches moments

I would like to find a algorithm that will do the following: Given two sets $A, B \subseteq \mathbb{R}$, where $|B| > |A|$, find the largest subset $C \subseteq B$, such that: $\qquad ...
1
vote
1answer
56 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 ...
1
vote
0answers
41 views

Applications of algorithms to stock trading analysis

There is a new Quantitative Finance SE site. However, I am interested in asking the "CS crowd": What are some interesting key references or surveys on applying algorithms to stock trading ...
3
votes
2answers
80 views

Genetic algorithm: What is the expected number of strings that are explored?

My question concerns genetic algorithm searching along bit strings. Given: $N$ = population size $l$ = length of bit strings $p_c$ = probability that a single crossover occur (double crossover ...
3
votes
0answers
41 views

What functions are easy to optimize?

Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function ...
0
votes
0answers
60 views

Is this problem a knapsack problem?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
1
vote
1answer
111 views

Efficiently pick a largest set of non-intersecting line segments

Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting? Brute force we would get $2^n$ sets to check where $n$ is the ...
3
votes
2answers
444 views

How does the 3-opt algorithm for TSP work?

I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers ...
1
vote
0answers
83 views

Is this NP-Hard problem? [closed]

I have the following problem. maximize $\sum\limits_{k=1}^Lx_k$ subject to: $\mathbf{x}^T\mathbf{A}~ \tilde{\mathbf{x}_i} \geq 0,~~ \forall~ i\in\{1, 2, \cdots, L\}.$ where, $~\mathbf{x}^T = (x_1, ...
1
vote
1answer
55 views

Local search: Problem with neighborhood definition

I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood ...
1
vote
2answers
72 views

Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ... ...
2
votes
3answers
99 views

A genetic algorithm modified for a specific problem

I have a problem whose solution can be written as a binary string with a given length $N$, where $N$ is a given parameter. Standard GA works well on this problem. From runs of small values $N$, I ...
0
votes
1answer
43 views

Using approximations to optimization problems for threshold problems

Many problems in computer science come in two flavors: Optimization problem: "Find an object with the largest size". Threshold problem: "Given $n$, find an object with a size of at least $n$, or ...
1
vote
0answers
34 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
1
vote
1answer
26 views

optimal placement of fixed length items on a given length

I have got some equipment of standard lengths, say: equipment_lengths = {60, 48, 36, 29} that I have to place on a given length of, say 100. I have to place this equipment so as to minimize ...
3
votes
1answer
86 views

Find subset with minimal sum under constraints

Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function. Now find $C' \subset C$ with ...
6
votes
1answer
45 views

Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP ...
3
votes
1answer
108 views

Clarification on Tabu Search

I need some help in understanding the 'Tabu Search' Algorithm. (Wikipedia) I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding. ...
3
votes
1answer
90 views

“Unusual” coupling between a decision problem and a corresponding optimization problem

There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case? Are there examples where the typical ...
0
votes
0answers
30 views

Help in developing a dynamic programming solution to this problem

I have asked this question on programmers.stackexchange but nobody was able to answer this question.I have asked for help on other forums but did not get much help.Since this is a part of my research ...
6
votes
4answers
2k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...