All Questions
69
questions
0
votes
1
answer
26
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
0
votes
0
answers
21
views
Filtering out faulty durations
I have a question that is algorithms and CS related but felt more appropriate to ask on Math Exchange.
I have a list of candidates, each with a given duration. for example {candidate1: 15s, candidate2:...
2
votes
1
answer
46
views
Maximal counterexample for a greedy approach with a non-canonical coin system
Let $1 = c_1 < c_2 < \dots < c_n$ be an integer coin system. This coin system is not necessarily canonical (that is, a greedy algorithm will not necessarily yield the fewest number of coins ...
1
vote
0
answers
47
views
Squared multiplicty minimization in multiple set choosing problem
The problem is the IOI 2007 competition's Sails problem. It has also appeared in Pranav A. Sriram Olympiad Combinatorics notes (Chapter 1 Exercise 14). I copied the problem description from Pranav. ...
- 11
0
votes
2
answers
62
views
Finding the minimum value of K for non-repeated sums
Given a set $A$ containing 10 positive integers, with the largest element denoted as $K$, we calculate all possible sums of elements from set $A$, including sums of 2, 3, 4, and so on, up to all 10 ...
- 143
1
vote
1
answer
318
views
Converting Undirected Graphs to a Tree While Preserving Edge Information
I'm working on a problem where I need to convert an undirected and unweighted graph with cycles into a tree while preserving the edge information (all the edges from the graph are preserved in the ...
- 11
2
votes
1
answer
126
views
Optimal strategy in number guessing game?
Consider the following game.
Two players each create a passcode using the digits 0-9 four times with repetition allowed.
The two take turns asking a yes or no question about the opponent's passcode. ...
- 21
2
votes
0
answers
84
views
How to solve this algorithmic task in Python?
I am trying to solve this task :
There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. second data on ...
- 139
1
vote
0
answers
46
views
How to solve this specific combinatorial optimization task?
I have problems with my combinatorial optimization task:
Different teams of the same company may have employees in different cities. If employees have the same position, we can change their teams (we ...
- 139
1
vote
1
answer
217
views
How to modify the hungarian algorithm for bipartite graphs with multiple edges with some already imposed connections
The Hungarian algorithm can be seen to take as input a complete weighted bipartite graph and outputs an optimal matching, maximising or minimising the sum of all the edges. Crucially, this algorithm ...
- 823
0
votes
0
answers
32
views
Effectively solve optimization problem in this system?
The system :
Given
$2$ sets $I,J$ such that $I\cap J = \emptyset , \#I = \#J$
a time-dependent function $c : \mathbb{R}_{\ge 0} \times I \times J \to \mathbb{R}_{\ge 0}$ .
Consider a system that ...
- 910
3
votes
0
answers
99
views
What set of angles uniquely defines a convex quadrilateral?
I am trying to characterize the set of angles in a (convex) quadrilateral that distinguishes it from any other quadrilateral that is not similar to it. Such a set will be said to uniquely define a ...
- 1,022
2
votes
0
answers
63
views
A (simple?) optimization question
I am looking for a way to optimize the function $f$, defined below.
First, fix some positive integer $k$ and let $c_1$ and $c_2$ be vectors in $\mathbb{R}^n$. Let $g$ be an increasing concave function ...
- 578
3
votes
1
answer
105
views
Show that a minimal solution has degree at most 2
Given a graph $G=(V,E)$, and a set $T\subseteq V$ of terminals, we say that $S \subseteq V\setminus T$ is feasible if $G[T\cup S]$ is connected.
In other words, a feasible solution is a set of non-...
- 578
0
votes
0
answers
160
views
NP completeness of a variant of assignment problem
I have the following variant of assignment problem:
Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ ...
- 422