Questions tagged [combinatorics]
The combinatorics tag has no usage guidance.
57
questions
0
votes
0
answers
28
views
Efficient PTAS for 2 identical knapsacks?
Input:
$v_1,v_2,...,v_n$ item profits,
$0<w_1,w_2,...,w_n\leq1$ item weights.
Output: $B_1,B_2$ which are subsets of $\{1,2,...,n\}$ s.t. they are disjoint,
and such that
$\forall i\in\{1,2\}:\sum_{...
- 1
1
vote
0
answers
39
views
Unclear relation in the number of permutations consistent with Hasse diagrams
I have been reading the paper 'Time Space Tradeoff for Sorting on Non-Oblivious Machines' by Borodin et al. (Link). Lemma 1 in that paper gives a relation between the number of permutations consistent ...
- 111
0
votes
0
answers
37
views
doubt about volume packing lemma for intersection of convex sets and lattices (repost from math SE)
Lemma 3.24 of Additive Combinatorics by Tao and Vu states the following:
Let $\Gamma \subset \mathbb{R}^d$ be a lattice of full rank, let $V$ be a bounded open subset of $\mathbb{R}^d$, and let $P$ ...
- 91
-1
votes
1
answer
76
views
Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$
I am able to solve this using brute force but curious if there is a better approach.
Given the function $F(A,B,C,D) = (A + B + C) / D$ where each variable is in the first 7 distinct values of the ...
- 1
4
votes
1
answer
192
views
Concrete version of KKL Theorem
The Kahn–Kalai–Linial (KKL) Theorem says that for any balanced Boolean function $f:\{−1,1\}^n→\{−1,1\}$ we have $\max_i {\bf Inf}_i(f) = \Omega\left(\frac{\log n}{n}\right)$. I am looking for a ...
- 1,242
2
votes
0
answers
86
views
Partition of a set of integers into subsets where the max. of the subset-sums is minimum
Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements.
Let $\mathcal{P}$ denote the set of ...
3
votes
1
answer
229
views
Cover a graph with complete graphs
I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
- 63
0
votes
0
answers
41
views
Combinations of subsets
Problem. Let $x = (x_1,...,x_N) \in K^{N}$, i.e., each element $x_j$ of $x$ can take $K$ discrete values. Let $x_{(i)}$, for $i \in 1,...,I,$ be a vector of overlapping subsets of $x$. For example, ...
- 101
5
votes
1
answer
214
views
Name for words without squared symbols
Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
- 161
1
vote
0
answers
61
views
Is this a variant of the set cover problem?
$\textbf{Decision Problem:}$
Given a finite set of elements $E$ and a collection $C$ of non empty sets, $C=\{E_1,...,E_n\}$, such that each $E_i$ covers at least one element of $E$. The goal is to ...
- 13
5
votes
0
answers
87
views
Does every graph of clique-width 3 have a large induced subgraph of clique-width 2?
Is there a constant $\alpha>0$ such that every graph $G$ of clique-width $3$ and order $n$ has an induced subgraph of order at least $\alpha n$ and clique-width at most $2$ (in other words, the ...
- 881
1
vote
0
answers
87
views
Is there a "common" name for this type of combinatorial optimization problem?
I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next ...
- 11
2
votes
0
answers
112
views
$k$-XOR collision free families
Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies:
$\forall i: v_i\in\{0,1\}^{z_{n,k}}$.
The bitwise xor ...
- 9,488
2
votes
0
answers
134
views
VC dimension of Voronoi cells (Manhattan distance)
If the distance function originates from the Euclidean norm ($l_2$-norm), then the Voronoi diagram of $n$ points in a compact subset of $\mathbb{R}^d$ consists of cells that are convex polytopes. In ...
- 46
1
vote
0
answers
134
views
Quantum error correction and graph codes
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
- 387
1
vote
1
answer
329
views
Intuition behind the Charikar's LP formulation for densest subgraph problem
I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper.
Just mentioning the LP for maximum density of a ...
- 23
2
votes
0
answers
119
views
Relation between automorphism group of a linear code and its dual code
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.
In ...
- 387
1
vote
0
answers
73
views
Combinatorial problems in electronics
This could be a downvoted question but I am asking because I am not able to get usable info via Google.
Are there any interesting combinatorial problems in the field of electronics circuits design? I ...
- 223
0
votes
1
answer
55
views
weights in low density codes
Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles ...
- 387
1
vote
0
answers
75
views
Sherali-Adams lowerbound instance of Unique Games constructed via CLT
The question comes from the following paper I have been reading:
[1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev.
Theorem 6.1 of [...
- 191
2
votes
0
answers
61
views
Complexity of Block Design?
What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)?
I've found one paper that creates approximately solutions using Metaheuristics that claims ...
- 29
-4
votes
1
answer
137
views
-1
votes
1
answer
194
views
Reducing resource allocation problem to bipartite matching
There are a set of bins, $B$ and a set of resources $R$. Each $b \in B$ is associated with a set function $Z_b(S) : 2^R \rightarrow \mathbb{R}^+$. The resource allocation problem is to find a ...
- 111
3
votes
1
answer
124
views
Results/concepts that also proved useful outside of their "home areas"
There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used ...
- 11.4k
4
votes
1
answer
268
views
Möbius values of CNF and DNF lattices of a monotone Boolean function
Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $...
- 1,431
3
votes
1
answer
81
views
Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ?
$$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$
Second question: if it is possible that every $L$...
- 1,077
6
votes
1
answer
152
views
Directed graph with bounded in-deg can be partitioned in a balanced way
I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
- 63
11
votes
1
answer
334
views
Distributing a binary relation into bins such that each element is in a small number of bins
We are given pairs of objects (say, numbers). Each object appears in at most $q$ pairs. Our goal is to distribute the pairs into equal-size bins, such that each object occurs in as few as possible ...
- 1,417
4
votes
1
answer
657
views
Interesting real life problem similar to subsetsum /bin packing problem
I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :
I have large number of cable reels/drums (let's ...
- 51
5
votes
1
answer
437
views
Enumerating all simply typed lambda terms of a given type
How can I enumerate all simply typed lambda terms which have a specified type?
More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in ...
- 672
3
votes
2
answers
2k
views
Binary rank of binary matrix
Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \...
- 639
2
votes
1
answer
573
views
Counting distinct set covers
I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the ...
- 143
3
votes
0
answers
110
views
On number of disjoint sets with small stack depth in a set of permutations
Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),
What is ...
- 31
1
vote
1
answer
151
views
What's a good advanced textbook/resource for studying the complexity of counting and combinatorics?
I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not ...
- 41
2
votes
1
answer
91
views
Complexity of generating a pseudo-Boolean function
A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to
$\mathbb{R}$.
Following is a pseudo-Boolean function.
$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - ...
- 661
23
votes
0
answers
2k
views
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and ...
1
vote
1
answer
580
views
Greedy vs LP Approximation
I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g....
- 171
0
votes
1
answer
125
views
An algorithm for counting to Graham’s Number
I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory.
I thougth of the way to organize counter suitable for ...
2
votes
1
answer
136
views
What is the standard name for the function which inflates a string by duplicating each of its characters?
Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters.
For ...
- 51
2
votes
0
answers
135
views
Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)
In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
2
votes
0
answers
347
views
Which complexity information of Ising model is more important?
In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
- 661
0
votes
0
answers
93
views
Single source multicommodity flow on a path or tree
Given a graph $G=(V,E)$, a set of terminals $T = \{t_1,\ldots, t_n\}$, and a single source $s$, where $s\in V$ and $T \subseteq V\backslash \{s\}$. Each terminal $i$ is associated with a demand $d_i$ ...
1
vote
0
answers
108
views
What are some examples where the Catalan numbers show up in algorithms/data structures?
For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
- 141
3
votes
0
answers
131
views
Social choice theory, preference aggregation data sets
I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social ...
- 39
2
votes
0
answers
92
views
A number-theoretic bijection in modular arithmetic
Fix an integer $n$. Considered as a multiplicative group, the sets $A = (\mathbb{Z} / n \mathbb{Z})^*$ and $B = \mathbb{Z} / \phi(n) \mathbb{Z}$ have the same cardinality $\phi(n)$, but it does not ...
- 1,292
3
votes
0
answers
228
views
Optimization of class schedule
I am creating a scheduling program that I need to either optimize or prove that what I have is already optimal.
I have n groups, all of which need to do some activity a in time slot t. A person can ...
13
votes
2
answers
326
views
Minimum amount of colors preventing an equilateral uniformly colored subtriangle
In the Bundeswettberweb Infomatik 2010/2011, there was an interesting problem:
For fixed $n$, find a minimal $k$ and a map $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that ...
- 607
1
vote
0
answers
111
views
Binary Search Tree DELETE survey
In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree ...
- 2,369
1
vote
0
answers
342
views
Bin packing upper bound: total size of items = k, bin size = r
Suppose you have items, whose total size (i.e. sum of sizes) is $k$.
The number of items and their individual sizes are unknown integers.
We need to pack the items into bins of size $r$.
I need to ...
- 31
2
votes
0
answers
252
views
Combinations over GF($q$)
Assume that we have $p$ finite sets ${m_1},{m_2},...,{m_p}$, with known cardinalities
${M_1},{M_2},...,{M_p}$, where $1 \le {M_i} \leq q$ ($i=1,2,...,p$).
Each set contains (distinct) elements, ...