Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

-1
votes
1answer
59 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 ...
3
votes
1answer
107 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 ...
4
votes
0answers
118 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 $...
3
votes
1answer
60 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$...
6
votes
1answer
121 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 ...
11
votes
1answer
303 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 ...
5
votes
1answer
166 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 ...
3
votes
1answer
262 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 ...
4
votes
2answers
538 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 \...
2
votes
1answer
210 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 ...
3
votes
0answers
105 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 ...
1
vote
1answer
85 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 ...
-2
votes
1answer
102 views

Partitions on Integer Permutations

Let $S_n$ be the set of all permutations of integers from $1$ to $n$. Let $P_1$ and $P_2$ be two partitions defined on $S_n$ as follows. $P_1$ is the set of all those permutations which have even ...
2
votes
1answer
75 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 - ...
18
votes
0answers
549 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
1answer
179 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....
0
votes
1answer
73 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
1answer
132 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 ...
2
votes
0answers
114 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
0answers
177 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 ...
0
votes
0answers
74 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
0answers
94 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 ...
3
votes
0answers
102 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 ...
2
votes
0answers
88 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 ...
3
votes
0answers
171 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
2answers
285 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 ...
1
vote
0answers
103 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 ...
1
vote
0answers
241 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 ...
2
votes
0answers
134 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, ...
5
votes
2answers
209 views

Probability for an element to appear in at least one set

Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct. What is the ...
6
votes
2answers
168 views

Difference Sets

Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
7
votes
2answers
364 views

Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no ...
1
vote
0answers
201 views

A non-trivial combinatorial optimization

So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be ...
2
votes
1answer
169 views

Locally monotone Boolean function

I am unable to understand the definition of locally monotone Boolean function which is defined in Gotsman and Linial, "Spectral Properties of Threshold Functions", 1994, p. 40: A function $f$ is ...
1
vote
1answer
93 views

PCVRP with prizes reduced over time

Hej guys, I'm working on customizing a Vehicle Routing Problem for a practical case, which is characterized as follows: The set of customers does not change over time, but their respective prizes ...
2
votes
0answers
58 views

Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: http://hal.inria.fr/docs/00/74/77/09/PDF/NonRedundantGeneration-TCS-2010....