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

-1
votes
2answers
58 views

Find the optimal way [on hold]

We consider the TSP in Grid-City. The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system. The distance of $2$ points $C=(x,...
2
votes
1answer
13 views

Similarity between Min-Conflicts and Coordinate Descent in CSPs?

I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction. I have came across the Min-Conflicts Algorithm which proved to be rather ...
3
votes
1answer
79 views

Closed form solution for optimization problem

Consider the problem of finding the real-valued matrix $C$ so that $$\|S-AC\|_F^2\qquad(1)$$ is minimal. ($S$ and $A$ are real valued matrices and $_F$ denotes the Frobenius norm). This problem has ...
1
vote
1answer
29 views

Approximate Nearest Neighbour Problem in Spherical Setting

There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving ...
6
votes
0answers
44 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how many permutations would get rejected ...
0
votes
2answers
112 views

Interval Scheduling Problem with Three Resources

So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem. Say there ...
2
votes
1answer
32 views

Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets

I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the ...
0
votes
1answer
47 views

O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question

Question: Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice. The second buy has to come after first sell. Solution: ...
3
votes
0answers
22 views

Knowing if I have an optimal ordering for a OBDD

I'm learning about OBDD and I have learned that the size of a reduced OBDD (ROBDD) is dependent on the ordering of the variables, and that finding an optimal ordering is an NP hard problem. Say I ...
0
votes
0answers
67 views

Non-convex optimization problem over graphs

Given integers $m,n$, I want to compute the maximum possible value of $\Phi(G)$, over all simple, connected, undirected, unweighted graphs $G$ with $n$ vertices and $m$ edges. The objective function $...
3
votes
0answers
56 views

Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
2
votes
1answer
24 views

NP-hardness of maximum set cover with even/odd coverage requirement

Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$ and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $...
0
votes
1answer
87 views

Algorithm for length of longest common subsequence

The case of multiple strings. A slight modification of the dynamic programming algorithm for two strings is used as a subroutine. Here is the pseudo code: ...
0
votes
0answers
52 views

What's the complexity of the problem of optimally distribute n balls in m boxes?

Assuming that there is a function $f(x)$ (non linear, non convex) where $x$ is the vector $[n_1,n_2,\dots n_m]$ where $n_i$ is the number of balls in the box $i \in \{1,\dots m\}$, and $\sum \limits_i^...
2
votes
1answer
47 views

Linear time algorithm for finding $k$ shortest paths in unweighted graphs

Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the ...
7
votes
2answers
590 views

Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
1
vote
1answer
30 views

Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
6
votes
1answer
92 views

Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
1
vote
1answer
30 views

Hyperplane through origin which goes through most number of points

Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects ...
3
votes
1answer
35 views

Algorithm to enclose a 2D-gridbased-room efficient

I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort. Here a little Example: In this example black squares are not ...
4
votes
1answer
29 views

How to find greatest set intersection of at least a given cardinality?

While dealing with a problem, I uncovered this subproblem: Input: A set of sets $S = \{S_1,...,S_r\}$ where $\mid$ $S_1$ $\cup$ ... $\cup$ $S_r$$\mid = n$, as well as a number $k<n$. Output: A ...
2
votes
1answer
20 views

Linear optimization or Constraint Satisfaction Problem with food

I was hoping someone could point me in the right direction in terms of what type of problem I am describing here so I can research it. My initial thought is that it is some form of Constraint ...
0
votes
1answer
53 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
48 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 ...
2
votes
1answer
227 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 ...
1
vote
1answer
33 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
42 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
36 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
55 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
86 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
31 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
34 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
137 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
19 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 ...
2
votes
1answer
24 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
39 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
42 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
307 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
36 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
49 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
38 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
55 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
18 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
156 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
31 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
20 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
36 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,...