Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

lifted mc algorithms API #22

Open
DerThorsten opened this issue Dec 21, 2015 · 1 comment
Open

lifted mc algorithms API #22

DerThorsten opened this issue Dec 21, 2015 · 1 comment

Comments

@DerThorsten
Copy link

@bjoern-andres why are the results of lifted mc algorithms passed by edge labels of the lifted graph.
I propose to use the connected comp. labeling of the orginal graph. And there should be the guarantee that this connected comp. labeling is valid wrt. the path constraints / lifted stuff (all nodes with the same number must be connected with a path in the orginal graph).

Also internally, algorithms could use that representation since it should be cheaper in memory.

@levinkov
Copy link

Both GAEC and KLj throughout their execution maintain a feasible solution. We do edge contractions only for the edges which define connectedness in the original graph, while KLj in each outer iteration performs projection onto the feasible set to make sure that components are connected by a path in the original graph. That's why we in verbose mode KLj prints both energy decrease as reported by the inner iteration and the one after projection onto feasible set. Special treatment of cut-vertices is computationally too expensive.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants