All Questions
24
questions
1
vote
1
answer
73
views
Generate superset with maximum overlap
I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
- 129
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
2
votes
2
answers
86
views
Is this problem NP-hard？Or what kind of mathematical problem does it belong to?
Assuming there are n types of gifts, each with a number of $a_n$. Now we have to pack them into gift packs, each containing several types of gifts, and each gift has only one.If a gift package ...
- 33
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
0
answers
35
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
1
vote
1
answer
146
views
How to assign tasks to a set of machines, given that the more tasks you assign to a machine the slower they will run? Bin covering with merging bins?
Intro
I need to design an algorithm that will distribute a known set of tasks with a known RAM requirement to a known set of machines with known RAM capacities. The tasks require a certain amount of ...
- 113
2
votes
1
answer
280
views
An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 922
0
votes
1
answer
53
views
Optimal Card Game Schedule
I have the responsibility of creating a schedule for a card game league. While creating the schedule, the following problem has arisen...
Let $n,g,s \in \mathbb{N+}$ where $s \leq n$.
Let $P = \{1, 2, ...
- 213
1
vote
1
answer
73
views
Trivial approximation ratio of $n/2$ for 2-Opt for TSP
I recently read that the 2-Opt algorithm for the TSP yielded an approximation ratio of $n/2$ by trivial reasons. However, there was neither proof nor further context provided and I am curious how this ...
- 177
3
votes
2
answers
147
views
Select five vectors that upon undergoing elementwise multiplication are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
- 31
0
votes
1
answer
535
views
Algorithm to find the largest intersection of sets
Edit:
I've tried to be more precise, clear up my examples, and to clarify the problem. Hopefully the problem makes more sense now.
The problem is this:
I have a list of sets $$S_1, S_2,... S_N$$ ...
- 171
7
votes
1
answer
132
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295
0
votes
2
answers
70
views
Maximizing a combinatorial identity
So here is my problem. If we have a vector $\textbf{x}=(x_1,...,x_n)$ where $x_j \in \mathbb{N}$ for each $j \in \{1,...,n\}$, then is there a way to maximize the value of the following combinatorial ...
user830143
1
vote
2
answers
100
views
Uniformly distribute N colored balls to P players, minimizing number of colors
I am facing the following combination problem :
I do have $B$ colored boxes, each one containing $N_b$ balls of the given color.
The total number of balls is thus $\sum_{b=1}^{B} N_b = N$.
I want ...
- 11
0
votes
0
answers
185
views
Greedy Algorithm on Knockout Tournaments: Proof of Correctness
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 ...
- 11