Questions tagged [optimal-strategy]

Finding an optimal strategy is common in games, where given a set of players the goal is to maximize the points of some fixed player. It is also common in resources allocation.

Filter by
Sorted by
Tagged with
4
votes
1answer
34 views

Is there a more efficient way to obtain the optimal input sequence in this finite-state system

Context: Consider $M$ finite state systems with evolution given by: $$ x^i_{k+1} = f(x_k^i,u_k) $$ where $x_k^i\in\{1,\dots,X\}$ is the state of system $i\in\{1,\dots,M\}$, $k\geq 0$, and $u_k\in\{1,\...
0
votes
1answer
55 views

Does this online problem have a specific name?

I came across the following online problem: Given a sequence of values of length n, the maximum value and the minimum value of the sequence, our goal: Given min and max, we want to find a good/best ...
1
vote
0answers
20 views

Discounted Optimal Stopping

The model is as followed: Consider an infinite horizon discounted problem $(0 < γ < 1)$ in which the state space is finite, with $n$ states, and there are only two possible decisions: stop or ...
0
votes
2answers
122 views

LQR optimal control of accumulator via dynamic programming

Let $$ x_{k+1} = x_k + u_k, \qquad x_0 = 5 $$ where $k \in \{ 0,1,2,3 \}$, define the return function $$ - \sum_{k=0}^3 \left( x_k^2 + u_k^2 \right) $$ with the following inequality constraints on the ...
0
votes
0answers
52 views

Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been ...
1
vote
1answer
58 views

solve a rational equation as fast as possible

I would like to find the first positive solution(if there is one) to this equation: $$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$ The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+...
0
votes
0answers
19 views

What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
1
vote
2answers
115 views

Best approach to resource allocation problem

Problem The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
4
votes
1answer
132 views

One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music. Problem Description Given a ...
2
votes
0answers
72 views

Maximize the minimum gap while scheduling within intervals?

Problem There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals? For ...
0
votes
1answer
57 views

Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?

Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time? ...
2
votes
1answer
30 views

Responsive input sliders - is there a better way?

I am building an app where a user controls inputs via multiple sliders each with discrete steps. The app then uses the combination of slider values to run some calculations and returns back an output ...
2
votes
1answer
36 views

Allocation of many students to many schools based on capacity

Say I have a set of schools coordinates (S). I also have a set of neighborhoods centroid coordinates (N). I know how many kids are in each neighborhood, and they are categorized as either primary, ...
1
vote
3answers
553 views

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
6
votes
0answers
224 views

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...