algorithms Questions - OR-Exchange

Checking whether a set family forms a matroid.

2010-06-04T20:43:08Z

Given a set family, what is the best way (empirically) to check whether the set family is equivalent to set of independent sets of some matroid. The input can be either the set family explicitly or bunch of cardinality constraints that must be satisfied. For example, given a universe E, subsets A_1,..,A_k of E and positive integers b_1,...,b_k, a set F is in the family iff |F\cap A_i|\leq b_i for each `1\leq i\leq k. Check whether the family is a matroid.

Theory behind local search methods

2010-04-22T03:06:45Z

From what I can gather, there is not much theory behind local search methods like Tabu Search, Simulated Annealing, Large Neighborhood Search, etc. By theory I mean some mathematical argument as to why these methods work in the cases that they do.

Despite that I feel there might exist some good theories about such methods that I would be interested in.

If someone knows of a good set of such references (maybe survey papers for instance), I would be grateful.

References for Submodular/supermodular optimization

2010-02-03T06:30:27Z

I am wondering if you know good references to learn about submodularity. I want to know the basics and perhaps some applications.

Other references about developing algorithms for optimization of submodular functions would also help.

Robust Group-Ranking Algorithms

2009-12-24T09:39:57Z

I am looking for a group-ranking algorithm (similar to Google's PageRank algorithm) that can help me solve the following problem:

In a large sparse graph every node can rate other nodes, an arc from node i to node j shows that i has rated j; and the arc-weight,r, which is a number in [0,1] shows how high the rating is. The graph is large (number of vertices>5000) and sparse (average number of adjacent arcs to each node is <5) many nodes do not have any adjacent arc coming in or going out and many only have incoming arcs, some only have outgoing arcs. Few have both incoming and outgoing arcs.

The question is how can we assign a ranking to each node such that the ranking is robust (a small group of nodes cannot push up their own ranking by down voting others)

I appreciate if you could please point out one or two valuable papers related to this question.

Note: If sparsity makes it difficult (or impossible) you can assume that the graph is dense.

Update It seems my problem definition was confusing. Here are some more explanations: Let's assume we have a web graph (although my problem is not related to the web at all). each page links to other pages. some pages are orphans (no incoming arc). But I want to rank the pages. Google does the same thing with their PageRank algorithm. Let's assume that the resulting Markov chain is irreducible and positive recurrent (it makes the problem much easier and better defined). The problem here is that each state rates only a subset of the state space.

The following are a number of related articles that I believe are very close:

I am looking for a public domain algorithm similar to HITS