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
0answers
25 views

Searching the best trading route - algorithm

Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount ...
2
votes
0answers
23 views

How to show that an MINLP with L0 regularization is NP-hard?

I am currently working on a project that involves a mixed-integer non-linear optimization problem, and wondering if I can state that this problem NP-hard in a research paper. I'm not looking for a ...
-1
votes
1answer
16 views

ordered uniform distribution

We are given $n$ objects with individual weights $w_1 , w_2 , \ldots , w_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m_i$ ...
-3
votes
0answers
39 views

Algorithm to solve a tangram [on hold]

I'm given a set of pieces and a shape, and I've to come up with one(any) solution. I'm totally stuck on where to begin. I'd like to get some suggestions to get me started. Particularly, I'd like to ...
1
vote
1answer
20 views

Travelling Salesman Problem with unknown shortest paths between nodes

I have a Travelling Salesman Problem, where I want to retrieve the "shortest" (approximate solution) circuit including the nodes n_1..n_n in a graph. The graph, however, includes a second set of ...
-3
votes
0answers
18 views

Maximum Flow and “eulerian” paths

I am working on the following exercise and I am not able to get any further. Imagine you are responsible for updating the Street View data for Berlin. You have k cars available starting at ...
2
votes
1answer
44 views

Shortest path from that passes through a set of edges once

Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big. Slow solution: Finding shortest ...
2
votes
3answers
48 views

How to calculate IV, EV and optimal k for K-means?

Could someone explain how to calculate the following 3 evaluative properties: Intercluster Variability (IV) - How different are the data points within the same cluster Extracluster Variability (EV) ...
2
votes
1answer
42 views

Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster. I'm currently trying to detect community using Louvain algorithm, but it ...
1
vote
1answer
61 views

smallest circle that covers two points with its center in x axis

I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know ...
0
votes
0answers
17 views

Parallel Machine Scheduling test data

I am writing optimization program for unrelated parallel machine scheduling problem on CUDA. Now, the only thing I am missing are some test cases. Does anyone know where I can find such data? I have ...
1
vote
0answers
41 views

Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles

Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when ...
0
votes
1answer
24 views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
1
vote
0answers
33 views

Create the shortest list that contains a set of subsets in block

I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list. The input is a set of set of ...
3
votes
0answers
49 views

Are coevolutionary “Free Lunches” really free lunches?

In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve ...
1
vote
0answers
30 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
6
votes
0answers
33 views

Linear functions of matrix exponential

Given a matrix $A$ and a vector $v$, I'm aware there are efficient algorithms for computing $e^Av$, where efficient means significantly faster than computing $e^A$ and multiplying by $v$. For a ...
5
votes
1answer
26 views

Evolutionary algorithm in stochastic environment

Consider the following model problem: I want to use an evolutionary algorithm to optimize the starting point of particles for which it is apriori clear where they would start in state space, but not ...
-1
votes
0answers
15 views

necessary and sufficient criterion for the solution of the dual problem in SVM [closed]

I'm studiyng the article "Support Vector Machine Solvers" of Bottou et al.[1] and i've problems to understand the reason why the optimality criterion expressed by the inequality (11) at page 8 is ...
-1
votes
0answers
21 views

hospital/residents problem prioritizes unmatched students from own university

The hospital/residents problem finds optimal hospital/resident matchings according to the residents' priorities while hospitals can take multiple residents. Is there an optimal solution of the H/R ...
7
votes
0answers
62 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
3
votes
2answers
46 views

Defining the goal function in an optimization problem

I have an optimization problem. There are a few quantities, call them $a, b, c$, that describe how good a solution is. However, they all have different priority, from highest to lowest: $a, b, c$. ...
1
vote
0answers
64 views

Maximum number of paths which do not use the same edge at the same time

Given a directed graph, consider the problem of finding the largest number of edge-disjoint paths from a source node $s$ to a destination node $t$. I know this can be done in polynomial time, for ...
1
vote
0answers
16 views

Get the max difference in an array for each day in nlogn [on hold]

So I'm having trouble figuring out a solution to this question. You’re a financial analyst, and have another stock market problem to solve. The input is A, ...
0
votes
0answers
23 views

Conjugate-Quasi-Newton [closed]

Does it make sense to workout an algorithm that combine conjugate gradient and Quasi-Newton? hk = -Bk-1 gk + bk hk-1 bk = (hk-1Tgk) / (hk-1T Bk hk-1) legend: k as iteration; h descent direction; B ...
0
votes
1answer
26 views

Finding top k which are the most different from each other

Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are. I want to ...
0
votes
2answers
52 views

Minimizing the overall cost over groups

I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this: ...
-1
votes
0answers
33 views

Minimizing the walking distance between walkways

I have the following problem: You are helping to design a new airline terminal. The terminal will have an extremely long hallway, and passengers will have to travel from one end to the other. To ...
3
votes
0answers
31 views

Speed up minimizing quadratic function by FFT

I'm trying to understand the following excerpt from a paper: Subproblem 1: computing $S$. The $S$ estimation subproblem corresponds to minimizing $$ \sum_{p}(S_p - I_p)^2 + \beta((\partial_xS_p ...
0
votes
0answers
28 views

Meta-Heuristics for bin packing problem [closed]

Dragonfly algorithm is a meta-heuristic algorithms. I am looking to apply it to solve the Bin Packing Problem. I don't understand how the search spaces would be build, the search conducted etc. Could ...
0
votes
0answers
18 views

Particle locating/collision prediction in bounded (two-dimensional) environments

I believe that many physics engines, particle simulators, and even video games use discrete-event simulation to determine where a particle or object is at any moment, and the direction in which it is ...
1
vote
1answer
31 views

Greedy algorithm for submodular optimzation

In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to ...
1
vote
1answer
32 views

TSP Edge Removal

Are there any papers/algorithms for finding edges in a graph that can be removed with affecting the graph's optimal TSP tour length? For instance, in a Euclidean TSP instance, many edges could be ...
6
votes
2answers
98 views

What is the intuition on why the longest path problem does not have optimal substructure?

I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think ...
2
votes
1answer
15 views

minimize $l_1$ distance between vectors

Given two vectors $a$ and $b$ I need to find $k$ such that $\sum_i|a_i - kb_i|$ is minimal. In other words, my goal is to find $k$ that minimizes the $l_1$ norm distance between $a$ and $kb$. How ...
5
votes
2answers
77 views

Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real ...
2
votes
2answers
47 views

TSP problem with a benchmark data

I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here. I'd started a ...
0
votes
2answers
20 views

Find k compatible objects with minimum total penalty

Assume we have a set of $n$ objects $X=\{x_1,x_2,\ldots,x_n\}$, where each object $x_i$ has a penalty $p_i$. Additionally, we have a set of incompatibility constraints $C=\{(x_i,x_j),\ldots\}$, where ...
1
vote
3answers
62 views

Travelling salesman very rough min and max estimates

Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the ...
3
votes
0answers
47 views

Branch and Bound running time and golden ratio

This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden ...
1
vote
1answer
47 views

Can the decision version of an optimization problem in NP, be in P?

It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore ...
1
vote
0answers
24 views

Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
6
votes
1answer
605 views

How to identify when to use Genetic Algorithm/Programming

I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem. TSP is basically a permutation/combination problem, and I can understand how GA helps ...
1
vote
0answers
96 views

When does Branch and Bound exactly stop giving solutions for the bin packing problem

I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time. I have N items (each item i has a volume ...
3
votes
0answers
30 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
4
votes
1answer
41 views

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . ...
0
votes
2answers
54 views

Longest substring with consecutive repetitions

I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring ...
0
votes
2answers
61 views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
1
vote
1answer
37 views

Is this some kind of hashing?

Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d ...
6
votes
0answers
122 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...