A highly correlated instance generator. More...

#include <generator.h>

Inheritance diagram for mosp::HighlyCorrelatedInstanceGenerator:

Collaboration diagram for mosp::HighlyCorrelatedInstanceGenerator:

Public Member Functions
	HighlyCorrelatedInstanceGenerator (int apps, int posts, double Density, double TieProp, int capacity)
	Create a new generator. More...

	HighlyCorrelatedInstanceGenerator (int apps, int posts, double Density, double TieProp, int capacity, int seed)
	Create a new generator. More...

void	GenerateGML (std::ostream &o)
	Generate a random structured instance in GML format. More...

void	GenerateGraph (leda::graph &G, leda::list< leda::node > &A, leda::list< leda::node > &B, leda::node_map< int > &capacity, leda::edge_map< int > &rank)
	Generate a random structured instance. More...

int	NumPosts () const

int	NumApplicants () const

Detailed Description

A highly correlated instance generator.

Highly correlated instances are problem instances where most of the applicants have a global and consistent knowledge of the posts reputation. Posts are already ranked, from an outside source, in some particular order $p_1, p_2, \ldots, p_m$ . This particular ranking is well known to all applicants and is gradly accepted, perhaps with a few minor adjustments per applicant. The goal is to have preferences which are based on the intuition that if two posts $p_i$ and $p_j$ are far in the global ranking from each other then it should be highly likely that they are far away in each applicant's ranking as well.

We model such instances based on the following parameters:

number of applicants ,
number of posts ,
a probability than an edge exists in our instance,
a probability that an edge is tied to its predecessor, and
capacity for all posts.

We create the instance in the following way. For each applicant $a$ we randomly sample with probability $d$ all posts, resulting in a subset $\{ p'_1, p'_2, \ldots\}$ . We sort this subset of posts based on the total order $p_1, p_2, \ldots, p_m$ . For each post $p'_i$ we create an edge $(a, p'_i)$ . We assign ranks as follows. We begin by giving edge $(a,p'_1)$ rank 1 and then we choose with probability $t$ whether to assign edge $(a, p'_2)$ the same rank as $(a, p'1)$ or to increase it. We continue this process for all remaining edges.

We call them highly correlated since preferences are highly related among applicants. These instances are particularly difficult with respect to popular matchings.

Constructor & Destructor Documentation

mosp::HighlyCorrelatedInstanceGenerator::HighlyCorrelatedInstanceGenerator	(	int	apps,
		int	posts,
		double	Density,
		double	TieProp,
		int	capacity
	)

inline

Create a new generator.

Parameters

apps	Number of applicants .
posts	Number of posts .
Density	Density parameter $0 \le d \le 1$
TieProp	Tie probability $0 \le t \le 1$
capacity	Posts capacity

mosp::HighlyCorrelatedInstanceGenerator::HighlyCorrelatedInstanceGenerator	(	int	apps,
		int	posts,
		double	Density,
		double	TieProp,
		int	capacity,
		int	seed
	)

inline

Create a new generator.

Parameters

apps	Number of applicants
posts	Number of posts
Density	Density parameter $0 \le d \le 1$
TieProp	Tie probability $0 \le t \le 1$
capacity	Posts capacity
seed	Seed value for the random number generator

Member Function Documentation

void mosp::StructuredInstanceGenerator::GenerateGML ( std::ostream & o )

inherited

Generate a random structured instance in GML format.

Parameters

o	Output the GML graph in this stream

void mosp::StructuredInstanceGenerator::GenerateGraph	(	leda::graph &	G,
		leda::list< leda::node > &	A,
		leda::list< leda::node > &	B,
		leda::node_map< int > &	capacity,
		leda::edge_map< int > &	rank
	)

inherited

Generate a random structured instance.

Parameters

G	The graph to return
A	The list of applicants
B	The list of posts
capacity	The node capacities
rank	The edge ranks

int mosp::StructuredInstanceGenerator::NumApplicants ( ) const

inlineinherited

Number of applicants that the resulting instance will have.

int mosp::StructuredInstanceGenerator::NumPosts ( ) const

inlineinherited

Number of posts that the resulting instance will have.

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation