The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
37 views

NFA-style representation of regexps which includes AND

I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for ...
0
votes
0answers
12 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
0
votes
0answers
15 views

Assignment Algorithm according to Habr – an alternative for the Hungarian Algorithm?

I've implemented the Hungarian Algorithm (aka Kuhn-Munkres-Algorithm) for a project, according to this Wikipedia article. It works fine, but has O(n3) time complexity. I use the method to generate a ...
1
vote
1answer
29 views

Similarity of two monochromatic shapes

I need to find out to what extent two shapes are similar. I mean I've got two vectors of points - and just that, no shadows, color or whatever - simplest case. Two triangles are the perfect example. ...
2
votes
1answer
26 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
3
votes
1answer
167 views

Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ ...
0
votes
1answer
82 views

Gale–Shapley algorithm is man-optimal

I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page ...
1
vote
1answer
50 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
0
votes
0answers
26 views

Algorithm to best match/cluster set of rectangles

The problem I'm working on is as follows. I've got a series of documents each containing a series of rectangles in Cartesian space. The goal is to create a best match of overlapping rectangles across ...
-1
votes
1answer
39 views

Stable marriage problem with more people then priorizations [closed]

I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex. My algorithm distributes all men and ...
1
vote
0answers
47 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
2
votes
1answer
220 views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
2
votes
1answer
49 views

Could an alternating approach yield a fairer solution to the stable marriage problem?

With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the ...
5
votes
1answer
59 views

Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
1
vote
0answers
104 views

Finding the number of distinct maximal matching in a bipartite graph [closed]

In a bipartite graph, how can we find the total number of ways of getting a maximal matching? The cardinality of both the sets in the bipartite graph may not be the same. So two matchings are said to ...
0
votes
1answer
37 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 ...
5
votes
1answer
177 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
60 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
185 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
73 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 ...
5
votes
1answer
225 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
75 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
223 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 ...
3
votes
0answers
44 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
136 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
62 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?
3
votes
1answer
1k 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
64 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
585 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
109 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
61 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 ...
9
votes
1answer
207 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
283 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
887 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
53 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
592 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
671 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
179 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
754 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, ...