Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

1
vote
0answers
33 views

Find subsets with one common item [on hold]

Given a set with $n$ items, find $x$ subsets, each one of them of size $y$, such that every two subsets share exactly one item. I've tried to solve it with a reduction to a graph, but I got lost... ...
5
votes
1answer
88 views

Efficient algorithm for 'unsumming' a set of sums

Given a multiset of natural numbers X, consider the set of all possible sums: $$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$ For example, ...
2
votes
0answers
39 views

Hardness of approximation for Disjoint Group Steiner Tree

Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group? The (intuitive) ...
1
vote
0answers
24 views

Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem

I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not ...
2
votes
1answer
45 views

What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]

I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
2
votes
1answer
48 views

Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
0
votes
1answer
41 views

Graph theory, $n$ people sitting around table [closed]

$n$ people want to have dinner together around a table for $k$ nights so that no person has the same neighbor twice. How big can $k$ be in terms of $n$? Does everybody get to sit next to everybody ...
1
vote
1answer
27 views

Combinatorial optimization - is there a formal name for this problem?

I am looking for a formal name and an algorithmic approach to the following problem. Given is a set of services each coming with a price: {s1, 300} {s2, 400} {s3, 800} Additionally there is a ...
2
votes
1answer
39 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
1
vote
1answer
40 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
0
votes
0answers
16 views

Time varying handshaking problem with memory: optimal matching

I have to analyse the following problem. I have a set of users $M = [m_0,m_i,\ldots,m_n]$. Between each pair of users I there is a certain Temporal Affinity $F$ defined as $F(m_i,m_j,t_k)$ that is: ...
3
votes
2answers
134 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
0
votes
1answer
63 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
-2
votes
2answers
77 views

Undirected graph G that has 12 vertices, 66 edges and 3 connected components?

Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?
1
vote
1answer
97 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
3
votes
0answers
90 views

permutations sampling by probability matrix

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = ...
0
votes
1answer
36 views

Is the number of nodes in an ORBDD 2n + 2?

Wikipedia says that the number of nodes in a ORBDD (Order Reduced Binary Decision Diagrams) of order $x_1 < x_2 < \dots < x_{2n}$ is $2n + 2$. But I can't find proof. Anyone?
5
votes
0answers
36 views

Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
6
votes
1answer
71 views

Algorithm to compose identity from a set of permutations

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity ...
1
vote
0answers
43 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
0answers
32 views

How many valid and unique Turing machines are there with restricted states and characters

This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of ...
6
votes
2answers
121 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
1
vote
1answer
52 views

Combinatorial optimization problem - What would you call this?

I'm trying to solve an optimization problem which can be described as follows. There are four sets objects. For simplicity, let's call them : Apples Oranges Pears Lemons The sets can contain ...
3
votes
1answer
63 views

Why isn't chess an impartial game?

In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions: (1) The game is finite; i.e. there is a ...
3
votes
1answer
69 views

Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
11
votes
2answers
329 views

Efficient algorithm to generate two diffuse, deranged permutations of a multiset at random

Background $\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak ...
-2
votes
1answer
51 views

How many ways are there to add a node to a digraph?

In a digraph with $n$ vertices, how many different ways a new vertex can be added to get the digraphs with $n$+1 vertices? Input digraph with $n$ vertices have following degree criteria : There ...
1
vote
1answer
22 views

Subset Sum algorithm, why not split by 3+?

A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of ...
0
votes
1answer
19 views

Allocating n processes to n servers, counting from the server perspective

In this question, I asked about a confusion I had counting the size of the sample space for allocation of n processes to n servers. Bangye gave a simple answer by approaching the counting problem from ...
0
votes
2answers
21 views

Number and probability of random allocations of n processes to n servers

I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space ...
4
votes
1answer
43 views

Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?

I've seen a few references [1], [2], [3] that say that for a Turing Machine with transition function defined by: $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ the number of ...
1
vote
0answers
16 views

Activity scheduling with activities that can move around

In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values: Duration: The length of time the activity takes Earliest time to start: The ...
1
vote
1answer
154 views

Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this: What is the minimum size of the largest clique in any graph with N ...
4
votes
1answer
47 views

Distribution of Ones in a Psuedorandom Sequence

Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table ...
6
votes
1answer
53 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
2
votes
1answer
116 views

How many permutations in a trainset?

If I have the following pieces to a train set: (12) Curve (4) Straight Such as this train set. I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. ...
2
votes
1answer
95 views

Computing a Sequence of People Entering and Leaving a Room

I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows. You start with an empty room and a group of n people waiting outside. At each step, ...
1
vote
2answers
178 views

How to find the Branch factor of 8 Puzzle

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that: Suppose,for example we wish to establish the ...
4
votes
2answers
77 views

Is the number of inequivalent elementary cellular automata rules really 88?

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
6
votes
1answer
39 views

The XOR cut-set structure, and combinatorial designs

Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$. Our goal is to preprocess ...
2
votes
1answer
72 views

Using a binary heap to solve an equation

I have to find a solution for this equation: I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n. $a^5 + b^5 = c^5 + d ^ 5$ I first thought ...
5
votes
1answer
118 views

Fast solution for a combinatorial maximizaton problem

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 ...
1
vote
1answer
219 views

Artificial intelligence - bridge and torch problem

I am doing a artificial intelligence course as part of my computer science degree. I am stuck on a question about searching. The question is a version of the Bridge and torch problem. Five people ...
0
votes
1answer
80 views

Binary digit problem?

Question: If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes ...
1
vote
1answer
33 views

Probability of having a log(n) length monotone subsequence in a random permutation of {1,…,n}

How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$. I wish to upperbound it with $1/n$.
9
votes
2answers
125 views

Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
1
vote
1answer
30 views

Filling a matrix with the sum of conditional values

I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$. I would like to Fill a square matrix $M$ of size $N\times N$ in the following way: $$\forall i,j ...
2
votes
0answers
162 views

Constructing orthogonal latin square Parker/Knuth method

I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square. The ...
1
vote
0answers
59 views

Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write $$\begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ...
1
vote
1answer
44 views

Smallest possible integer not obtained from sumset

Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A) What is the best way of finding the ...