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
0 votes
1 answer
33 views

Guessing number game "hot" or "cold"

I thought up this problem and am trying to come up with an optimal solution. I am thinking of a number uniformly randomly between 1-100, inclusive. If you guess the number, you "win". Else ...
user avatar
  • 11
1 vote
0 answers
38 views

How to find optimizers with computer in this kind of minimax problem [closed]

I have a minimax problem of the form $$\max_{\substack{u_1,\dots,u_n \ge 0 \\ u_1+\dots+u_n = 1}} \min_{\substack{v_1,\dots,v_m \ge 0 \\ v_1+\dots+v_m = 1 \\ v_{j_1} \le v_{j_2} \hspace{1mm} \forall (...
user avatar
1 vote
2 answers
55 views

Variant of the Knapsack Problem 0-1 - One item from each set and zero-weighted items

I understand the basics of the 0-1 problem and its solution. I have a variant of it that I'm trying to solve in a decent way and I'm struggling on it, mostly because of the 0-weighted items. These are ...
user avatar
  • 11
3 votes
1 answer
74 views

Allocating m rooms of varying capacity to n booking requests of varying sizes

I am developing a system which performs automated room allotment. We have finite number of rooms, each with varying capacity. Each booking request is also of varying size. The goal here is to minimize ...
user avatar
1 vote
1 answer
36 views

Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?

In the Optimal Substructure Wikipedia, As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to ...
user avatar
4 votes
1 answer
35 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,\...
user avatar
0 votes
1 answer
62 views

Does this online problem have a specific name?

I came across the following family of online problems: 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 ...
user avatar
1 vote
0 answers
25 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 ...
user avatar
0 votes
2 answers
132 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 ...
user avatar
0 votes
0 answers
60 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 ...
user avatar
  • 13
1 vote
1 answer
64 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+...
user avatar
1 vote
2 answers
170 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 ...
user avatar
4 votes
1 answer
136 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 ...
user avatar
2 votes
0 answers
92 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 ...
user avatar
0 votes
1 answer
59 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? ...
user avatar
2 votes
1 answer
31 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 ...
user avatar
  • 121
2 votes
1 answer
38 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, ...
user avatar
1 vote
3 answers
676 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 ...
user avatar
7 votes
0 answers
238 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 ...
user avatar
  • 101