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

0
votes
0answers
16 views

Optimize Eve Online ship fitting, highly combinatoric composition - what methods?

In MMO RPG "Eve Online", where's a problem of composing spaceships from parts (fitting) optimally for the player. The problem consists of many parts: player skills, brain implants, ship hull, ...
0
votes
1answer
49 views

Discrete optimisation in 5 variables

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, ...
0
votes
0answers
31 views

Planning interviews

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps). Problem is: Everyday I am receiving job offers, and I have to ...
1
vote
1answer
104 views

Finding all soldier wins

Consider the following game (see also this question): One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On ...
-3
votes
0answers
12 views

Share PDF files with permissions [on hold]

in my office we share PDF Files company wide via email but they have to email us back to say who they're sending the PDF to. Is there a way to automate this process maybe using an online hosting ...
-3
votes
0answers
22 views

Bootcamp or self-teach? [closed]

Who out there is experienced a little bit with both and might be able to provide an answer here? I'm finding it very difficult to self-motivate at home, push through the walls, and even though it's a ...
1
vote
1answer
27 views

Project to nearest point in convex polytope

Is there a reasonably efficient algorithm for the following task? Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$ Find: a point $y \in \mathcal{C}$ that is ...
1
vote
0answers
34 views

calculate minimum wrapping surface area required for packing boxes

I can't get this question out of mind and can't come up with a algorithm to solve this Problem Given a set of N boxes, all of which have identical w x l x h dimensions, print the minimum ...
-1
votes
1answer
33 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
3
votes
0answers
48 views

Maximizing pruned branches in an alpha-beta tree

Preliminary After doing some searches of similar questions posted here and elsewhere, i feel like this is the right place to inquire about, now let's get through some boring main notations... A ...
-1
votes
1answer
70 views

Cost Minimizing

A man has to travel for given number of days by bus. He can buy either: $1$ day ticket for $2Rs$ (valid for 1 day) $7$ days ticket for $7Rs$ (valid for 7 consecutive days) $30$ days ticket for $25Rs$...
3
votes
1answer
29 views

Snap/Fit a chain of lines to points

I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it. Here is ...
0
votes
0answers
31 views

Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
0
votes
1answer
30 views

It is necessary to minimize the functional

Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height ...
2
votes
2answers
131 views

Computing maximum-cost subtree that uses at most k edges

I'm looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$ Output: the maximum-cost subtree containing $\le k$ edges ...
3
votes
0answers
26 views

How approximable is time-bounded Kolmogorov Complexity?

Given a Turing Complete Language, the optimization problem would be: Given inputs x and S, where x is a finite binary string and S is a limit on steps, find the shortest program in that TC language ...
3
votes
0answers
43 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
3
votes
1answer
18 views

Project to L1 ball of specified radius

The task If $x \in \mathbb{R}^d$ is a $d$-dimensional vector, recall that the $\ell_1$ norm of $x$ is given by $$||x||_1 = |x_1| + |x_2| + \dots + |x_d|.$$ The $\ell_1$-ball of radius $\lambda$ is ...
1
vote
1answer
20 views

Good resources for understanding semidefinite relaxation for combinatorial problems

I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as ...
2
votes
0answers
37 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
0
votes
0answers
41 views

Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
5
votes
2answers
303 views

Is this an instance of a well-known problem?

Context I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I ...
1
vote
0answers
35 views

Create an array minimizing sum of square deviations to another array

Problem Let y be an array of float numbers (of length $n$) bounded in the range [0,1]. I am trying to compute the array x that ...
0
votes
1answer
47 views

0/1 Knapsack problem with overlapping items

Here's a doozy: Given a knapsack with a capacity W, and n overlapping items (definition of overlapping to follow), which items should we take to maximize the value of the knapsack? In this problem, ...
1
vote
1answer
37 views

How can I reduce a product of transpositions?

I'm looking for an algorithm to solve the following task: Input: a set $T$ of transpositions; a permutation $\pi$ expressed as a product of transpositions from $T$ Desired output: express $\pi$ as ...
1
vote
1answer
45 views

Why is bipartite graph matching hard?

I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me ...
2
votes
0answers
17 views

Is there any example of Regression Tree driven optimization (or active learning)?

Bayesian Optimization is the classic example of meta-model driven optimization where new observations are used to train a Gaussian process that provides a clue to where to optimize next. LEM (...
3
votes
1answer
154 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 <...
3
votes
0answers
30 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
18 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$ ...
1
vote
0answers
29 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 nodes,...
2
votes
1answer
55 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
54 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
49 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
64 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
18 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
44 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
56 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
40 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
50 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 two-...
1
vote
0answers
31 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
35 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
31 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 ...
7
votes
0answers
76 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
49 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
69 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
17 views

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

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
1answer
30 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
54 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: ...
3
votes
0answers
32 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 ...