A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
71 views

Polynomial LP-based algorithm for cost minimization of DAG weights modification

Given a DAG $G=(V,E)$, with non-negative weights $ w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that: $\forall u,v\in V$ and $\forall p_1\neq p_2 $ paths from $u$ to ...
6
votes
2answers
1k views

Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once? I'd like to know if there is a general approach to this ...
0
votes
3answers
797 views

Modification of Dijkstra's algorithm

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality? There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
12
votes
1answer
361 views

Is packing a bag of presents easier for Rupert than Santa?

Or: Do we need Rupert in order to get presents at all? Routing issues aside, Santa faces the following problem (many, many times over): Given a bag with capacity¹ $C$ and a set of presents $\{p_1, ...
5
votes
1answer
94 views

Location Selection Algorithm in Solar Engineering

This is a practical problem in energy generation with heliostats. We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One ...
1
vote
1answer
259 views

MAX SAT Optimization problem

search problem: find the assignment that maximize the number of satisfied clauses For decision problem: determine whether there is an assignment that satisfies k of clauses. optimization problem : ...
2
votes
1answer
145 views

Proof that multi-armed bandit optimization has exponential regret if loss function is general

I was reading Robert Kelinberg's paper on Nearly Tight Bounds for the Continuum-Armed Bandit Problem There is a section where he says: "For a d-dimensional strategy space, any multi-armed bandit ...
0
votes
0answers
46 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
1
vote
1answer
79 views

Can you help Sam?

Sam is a teacher. He teaches exotic materials (he's not a very computer fluent person and knows no programming). In his course he has several topics he teaches, say $a$, and each topic has a variable ...
2
votes
2answers
85 views

Min-max the component-wise sum of two sets

When I was trying to prove a problem at hand to be NP-complete, I coined the following problem: Given two integer sets $A = \{ a_1, \cdots, a_n \}$ and $B = \{ b_1, \cdots, b_n \}$. We know that ...
-3
votes
3answers
164 views

Building a Hyper Computer

I had an idea for a theoretical super computer. Supposing, one was able to optimise(or significantly increase efficiency) all algorithms used in most computing tasks(An open source project on ...
1
vote
0answers
113 views

Given a digraph and a root, find a tree that minimizes the sum of edges

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$. Solution: A directed tree with root $v$. Objective: Minimize total weight. My formulation: ...
-1
votes
1answer
77 views

Algorithm : Select maximum number of Boxes to lift from N boxes

There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to ...
1
vote
0answers
60 views

How to merge all 3-grams into smallest possible string?

There is a set of all possible letters: $A = \{ a, b, \ldots, z \}.$ Then the set of all possible 3-grams looks like that: $A^3 = A \times A \times A = $ $\{$ $\;\;(a, a, a), $ $\;\;(a, a, b), $ $\;\;(...
1
vote
1answer
281 views

There are n numbers. Find the maximal set of pairwise NON coprime numbers

I have to take input in an array(no. of elements in array <=10^5). For ex:- Let the array be {2,3,4,16,9,45,81,27} Now I need to find the order of the maximal set such that any pair of elements in ...
3
votes
1answer
116 views

Performance gain by implementing streamlined simplex

I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of ...
7
votes
1answer
155 views

Branch and bound for minimum linear arrangement

I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost. Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , ...
2
votes
0answers
41 views

Identify common mathematical problem behind my task in scheduling area

Having single operator, which could do work and it's time of availability - for example from 8 am till 9 pm. And operator have limited resource - let's call it ...
8
votes
1answer
259 views

How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?

The real problem I am facing is the following. INSTANCE: I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}>0$ for all $i\in K$ and $j\in N$. QUESTION: I need to find a ...
3
votes
1answer
576 views

Can you solve 3D Tic Tac Toe with Minimax?

I have implemented a 3d Tic Tac Toe game with AI, where the computer is unbeatable. The only thing is that the board looks like this: _ _ _ _ _ _ _ _ rather ...
27
votes
2answers
1k views

Selling blocks of time slots

Given $n$ time slots that $k$ people want to buy. Person $i$ has a value $h(i,j)\geq 0$ for each time slot $j$. Each person can only buy one consecutive block of time slots, which could be empty. ...
14
votes
5answers
1k views

How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

I have an algorithmic problem. Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$. For example: If $T$=[1, 3, 4, ...
0
votes
0answers
268 views

Eggs and Floors Puzzle - Alternate

Recently I've run across the "Two eggs, 100 floors" problem: You are given two eggs, and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which ...
1
vote
1answer
545 views

Efficiently find maximum XOR on a graph

We are given an undirected graph $G=(V,E)$, $|V| \leq 50$. We are also given a starting vertex $s$. Each vertex $v$ of the graph is associated with a natural number $N_v$. Initially our profit is $R=...
0
votes
1answer
79 views

Is my implementation of genetic algorithm correct?

In genetic algorithms, we have a function called "mutation". Before we call this function, we choose parents. In my version of the algorithm, when i mutate the child, i don't change the bits which ...
2
votes
3answers
2k views

How can I generate Rubik's cube algorithms equivalent to a given algorithm?

I am developing a computer program that solves the Rubik's cube. It is not anything advanced nor fast. It solves the cube by the Friedrich method, using algorithms that I use in real life to solve the ...
3
votes
1answer
519 views

Understanding the bandwidth problem on graphs

I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list: ...
2
votes
0answers
183 views

Is there a name for the knapsack problem with no bound on knapsack capacity?

I am investigating heuristics for optimising the packing a fixed number of knapsacks with a set of items of defined weights, however the knapsacks do not have a defined capacity limit. The objective ...
4
votes
1answer
310 views

MDS minimization with gradient descent

I have the following multiple dimensional scaling (MDS) minimization problem in vectors $v_1, v_2, \dots, v_n \in \mathbb R^2$ $$\min_{v_1, v_2, \dots, v_n} \sum_{i,j} \left( \|v_i - v_j\| - d_{i,j} \...
2
votes
1answer
109 views

Assignment algorithm for symmetric matrices

I stumbled on the Hungarian algorithm during my personal research when I was assigned interesting problem as homework: Given a list of objects $L$ and a pairing function $\delta : L \times L \...
5
votes
1answer
154 views

Optimization over convex combinations in a circle

Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product $$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$ where $P$ is a point on the circle and $d$ are ...
5
votes
1answer
421 views

Heuristic algorithms for the dense assignment problem

Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or ...
-1
votes
1answer
133 views

Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
2
votes
2answers
44 views

Growing a set given constraints

I am trying to solve the following: Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to: $\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = ...
5
votes
1answer
38 views

Find expression with minimal distance to target

I will start of with an informal example and give a more formal problem definition later. Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and ...
2
votes
1answer
332 views

Understanding the Diameter Constrained MST Problem

I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). I don't think I understand it as I should. Here is how I understand ...
7
votes
1answer
236 views

Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
4
votes
0answers
115 views

Complexity of a non-linear knapsack problem

Minimize $$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$ subject to $$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$ $$v_{i,j}\in\{0,1\}~\forall i,~j$$ where $w_{i,j}$ and ...
3
votes
1answer
79 views

Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language): ...
0
votes
2answers
3k views

Dynamic Programming vs Greedy - coin change problem

This is a fairly common problem: Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible. Given an input of powers of $p$, ...
0
votes
0answers
116 views

Algorithm: How many symbols of occurence k fit into b buckets under condition

I have the following problem to solve: Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size. Place ...
0
votes
2answers
134 views

A specific version of a job scheduling problem

I'm looking for a solutions or book references to a given variation of a job scheduling problem: Given $n$ machines (let's denote it by $m_1, m_2, \ldots, m_n$) and $r$ tasks ($t_1, t_2, \ldots, t_r$)...
0
votes
1answer
366 views

Using AI / Machine learning to find the most time and space efficient solutions to an algorithm [duplicate]

As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms. Is it forseeable in the future that we have languages or techniques such as AI/...
1
vote
1answer
159 views

Making mathematical expressions as balanced trees as possible

I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible. This is what I have done so far, but is there a way to make them even more ...
1
vote
0answers
130 views

FPTAS, except not polynomial in size: which class?

Problems in FPTAS require time which is (at most) polynomial in problem size. Suppose this last requirement is relaxed. What is the corresponding approximability class and where can one read about it? ...
1
vote
1answer
327 views

An algorithm to find the maximum profitable assignment

Given a set of workers $w_1,...,w_m$ and and a set of tasks $t_1,...,t_n$, and a $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be ...
2
votes
2answers
881 views

Anyone knows an algorithm that finds minimum distance for all permutations?

Let $A$ and $B$ be two finite sets of the same size $n$. Let $P(A),P(B)$ be the set of all permutations of $A,B$ respectively. A distance function $d(a,b)$ is defined for any $a\in P(A),b\in P(B)$. We ...
2
votes
1answer
4k views

Single-Source Shortest Path with at most k edges using Dijkstra's algorithm

I am trying to solve a bounded SSSP problem as follows: Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with ...
4
votes
0answers
219 views

Subset sum with wider constraint

The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$: $ max \displaystyle\sum_{i} x_i, x_i \in \{0,1\} $ subject to $ \displaystyle\sum_{i} w_ix_i \leq W $ for a ...
5
votes
2answers
691 views

What is the optimal way to cut B chocolate bars to share equally between N people?

What is the optimal way to cut B chocolate bars to share equally between N people? Here is an example of different cuts for B = 5 chocolate bars and N = 6 people. Strategy 1: cut each chocolate bar ...