The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
34 views

Matching with dependencies

I have a matching problem which I find is rather different from the stable marriage problem. I have four sets $A,B,C,D$. Elements of set $A$ have to be matched with those of $B$ and $C$ is to be ...
0
votes
1answer
27 views

Algorithm for distributing members over activites (with individual preferences)

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils ...
4
votes
1answer
143 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
1
vote
2answers
38 views

Algorithm to match timestamped events from two sources

does a good known algorithm exists for this problem? On input I have two series of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned. ...
1
vote
1answer
90 views

Why can't we solve the dinner party problem by finding a maximum matching?

Consider the following dinner party problem: Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of ...
2
votes
1answer
54 views

Bipartite Matching in the Plane

I'm currently working on a problem that I came across: You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
4
votes
1answer
85 views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
1
vote
1answer
68 views

Are algorithms for searching text vs searching numbers fundamentally different?

I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially. I save a draft in gmail with the content ...
3
votes
2answers
186 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...
2
votes
0answers
33 views

variant of the stable roommates problem

The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the ...
2
votes
1answer
98 views

Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the ...
2
votes
1answer
38 views

What's the dual problem of stable matching?

So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?
2
votes
1answer
296 views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
2
votes
1answer
42 views

Number of Matchings in a Bipartite

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices ...
2
votes
2answers
336 views

Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

There is one point I don't understand in the DFA construction for mismatch cases. Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction ...
0
votes
1answer
83 views

Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

I am new to this and an amateur... please help. My Question in practical terms: Given The three following inputs... determine the number of unique group arrangements as an ordered set. INPUT: 'a' = ...
2
votes
0answers
56 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing ...
7
votes
1answer
122 views

Sampling perfect matching uniformly at random

Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am ...
3
votes
1answer
225 views

Assignment problem with no cost

I have a problem that I was able to conceptualize as following: Problem We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination ...
8
votes
2answers
589 views

An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?

This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better. I'm ...
3
votes
1answer
43 views

Is matching with mismatches a special(parametrized) case of Closest String problem?

I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the ...
3
votes
2answers
287 views

Proof of the Stable Matching Problem

Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem. Theorem 1.2.3 - page 12: In a man-optimal version of stable matching, each woman has worst partner that ...
1
vote
2answers
309 views

The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
2
votes
2answers
152 views

Maximum weight matching

There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted ...
1
vote
1answer
505 views

3-dimensional matching approximation algorithm (implementation details)

I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below: How can I construct the maximum matching M_r in S_r in linear time in line 8? $X, ...