2
votes
0answers
46 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
2
votes
0answers
26 views

Find spacing of fence posts with minimal distance to fence posts of two other fences

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ...
0
votes
1answer
13 views

Max no. of piece in k cut

Suppose I have large piece of rectangular sheet. Cutting is allowed only vertically and horizontally. My approach is if no. of cut is even then max. no of piece is (n/2)*(n/2) if no of cut is odd ...
0
votes
0answers
22 views

To minimize surface area of integer cuboid of ​​the known volume

There is a cuboid (a * b * c), (a, b, c ∈ N). S (Surface area of a cuboid) = 2 * (ab + bc + ca). V (Volume of a cuboid) = a * b * c = n. I need to minimize S, provided that I specified the volume ...
0
votes
0answers
22 views

Adjust previous optimal solution to new assignment problem

Suppose I have an assignment problem with $n$ workers and $n$ jobs and its optimal solution. Now another worker and another job comes along and we are given all new costs. Is there an efficient ...
0
votes
1answer
27 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...
0
votes
0answers
47 views

How can we find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits?

If $n$ and $m$ extremely large (1000 digits) and $1 <\frac{2^m}{e^n} < e$, how can we create an effective algorithm to find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits (10 digits ...
2
votes
2answers
115 views

How to find the optimal mapping between two sets?

Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's ...
1
vote
0answers
26 views

Details of the Goldberg-Radzik algorithm for computing shortest paths

I'm trying to implement the Goldberg-Radzik algorithm, which is described in the 1993 paper "A heuristic improvement of the Bellman-Ford algorithm" by Andrew Goldberg and Tomasz Radzik (link: ...
3
votes
2answers
39 views

Smallest value taken by a quadratic polynomial in two variables.

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following: Problem 1: Given ...
0
votes
0answers
36 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
6
votes
1answer
129 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
3
votes
0answers
116 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
1
vote
0answers
44 views

Alternating Direction Method of Multipliers (ADMM) application

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form: $\min \text{ } f(X) + g(Z)$ $\text{s.t. } AX + BZ = C$ where $X$, $Z$ and $C$ are real ...
0
votes
1answer
35 views

Evolutionary algorithm

Can someone provide me a good reference for the CMA-ES algorithm? I'm new in the world of optimization and just reading the author reference doesn't help me a lot. I know the basic idea of a genetic ...
3
votes
2answers
27 views

Smallest linear combination of a set of vectors

I'm searching for an algorithm to accomplish a (hopefully) simple task. If I have a set of vetors, (e.g. $\left( ...
0
votes
0answers
31 views

Alternative to Hungarian Algorithm to determine minimum cost?

Is there a graphic calculator (CAS technology) method to solve minimum cost problems/allocations that are normally completed with the Hungarian Algorithm... Hungarian Algorithm is time consuming, ...
2
votes
0answers
47 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
2
votes
1answer
77 views

How can I find the point (X, Y, Z) which minimizes this quantity?

I have a number of equally powerful light sources $L_i, 1 \le i \le N$ at points within a cube $(x_i, y_i, z_i), -1 \le x_i, y_i, z_i \le 1$. The intensity of each light falls off with distance ...
3
votes
2answers
48 views

Largest Equilateral Triangle in a Polygon

Is there an algorithm to determine the largest equilateral triangle in a convex polygon?
2
votes
1answer
21 views

How to efficiently compute the pareto front in a >2 dimensional multi-objective case?

I'm currently working on an optimization problem with 4 different objective functions and need an algorithm to compute the pareto frontier from several "solutions" to that problem. I already found ...
0
votes
0answers
40 views

Global optimization

Assume that I want to find the global minimum of a non-linear, non-convex, multidimensional function subject to several restrictions. Could you recommend me any deterministic strategy which can ...
0
votes
0answers
51 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
3
votes
0answers
21 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
3
votes
2answers
56 views

Minimize Sum a_i / Sum b_i over subsets

I have two positive finite sequences $a_i$ and $b_i$, with $0 \leqslant i \leqslant n$. The problem is to find the subset $I$ of $\{0, ..., n\}$ that minimizes: $$\frac{\sum_{i \in I} a_i}{\sum_{i ...
1
vote
2answers
280 views

Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$. Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$ with $c \in \{1, 2,\dots ...
0
votes
1answer
45 views

Concrete Example of Maximum Likelihood Estimator

I was reading this article, about how seatgeek creates its algorithm for choosing the optimal seat: http://chairnerd.seatgeek.com/the-math-behind-ticket-bargains Most of it is straightforward up ...
0
votes
0answers
19 views

Quantization minimizing the quadratic error

I am working on a quantization problem which could be express in these terms : Given a set of positive reals $\{x_1, x_2,\dots,x_M\}$, I need to find another set $\{y_1,y_2,\dots,y_N\}$ of size $N ...
0
votes
1answer
39 views

Assigning workers to tasks such that difference of the number of workers for each task to a given optimum is minimized

Im trying to find an algorithm to solve the following problem: We have a set of workers and some tasks, with not every worker being able to do any kind of task (but at least one). Theres is ...
2
votes
2answers
46 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
0
votes
0answers
37 views

Keller 6 graph and maximum clique

Based on the DIMACS maximum clique benchmark, http://iridia.ulb.ac.be/~fmascia/maximum_clique/, the Keller 6 graph contains a clique of size 59. The clique number however is at least 59 (as can be ...
2
votes
3answers
45 views

How to combine Unitary Matrices in a clever way?

I am trying to implement genetic-type algorithms on unitary matrices. Hopefully I should be able to use this question for the mutation part. But I am having an issue with the cross-over step. So here ...
0
votes
1answer
32 views

Halting of an algorithm

Suppose there is an algorithm that runs on a finite set. If we do not directly specify a halting condition, such as reaching a certain value, or after given number of iterations, what are the methods ...
0
votes
0answers
45 views

Maximizing variance of Hamming distance of a system

I have a system as shown below, where 4 registers have 8 bit input A,B,C,...
1
vote
1answer
34 views

Reverse engineering the objective function

If there is a finite iteration algorithm can we find a function that this algorithm optimizes, in hindsight? Edit: Suppose there is a set of functions $f_i(x)$, where $x\in \mathbb R^n$, ...
0
votes
0answers
36 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
1
vote
0answers
42 views

Conjugate Gradient Method Near Exact Line Search

Unlike Newton-type methods, there is no natural step-length value $\alpha _k$ in conjugate gradient methods. Because of this, why do we need to use a near exact line search if we are to expect rapid ...
3
votes
1answer
111 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
0
votes
0answers
43 views

Need suggestions for this real world problem

I have a real-world optimisation problem. Following is the problem. At last have the hope for mathematics. Problem: One person Mr. X works as supervisor for a home appliances repairing company. Mr. X ...
0
votes
1answer
34 views

Is it possible to always get the optimal formula regardless of the derivation method?

Today I've tried to solve a geometric problem (collision point between two circles in a specific situation). I found a working solution but I'm not sure if it was optimal (maybe my solution took more ...
0
votes
1answer
45 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
2answers
32 views

Minimize error function with integer constraints

Much time has passed since I studied any form of math so I wanted to take this cheap shot of asking someone else to think for me. I need to write some software that, for any given real number ...
0
votes
0answers
31 views

Bound for the greedy algorithm solution to the cover set problem

This is from Algorithms by Dasgupta et al.: Claim Suppose B contains $n$ elements and that the optimal cover consists of k sets. Then the greedy algorithm will use at most $k$ ln $n$ sets. ...
1
vote
1answer
140 views

Which greedy algorithm is optimal?

The following question is a homework problem for a course called Design and Analysis of Algorithms. In the problem, there is a minimized cost function and two greedy algorithms. I am asked to show ...
0
votes
3answers
64 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
1
vote
1answer
16 views

How to recognize if an algorithm working on ordinal data will also work if the ordering is reversed?

Inspired by a comment on this question. Assume that I have an algorithm which uses ordinally scaled data. The algorithm in the original question was the solution of the Secretary Problem. It uses ...
0
votes
0answers
15 views

chained max notation

I'm confused on how to implement a quality indicator for multi-objective optimization. I don't understand the following notation. $$I_{\epsilon} (A,B)=\max_{z^2 \in B} \min_{z^1 \in A} \max_{1 \le i ...
0
votes
2answers
65 views

Find $n$ and $k$ such that maximum element is minimum

Given $a_1, a_2, a_3, \ldots, a_m \in \mathbb {Z}$. How do I find $n \in \mathbb Z, k \in \mathbb N$ such that $$\max \{|n - a_1|, |n+k-a_2|, |n+2k-a_3|,...\}$$ is minimum? The original problem was ...
1
vote
0answers
21 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
2
votes
1answer
66 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...