Small Combinatoric Optimization Benchmarks

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

You are currently reading a thread in /sci/ - Science & Math

Thread images: 1

Anonymous

Small Combinatoric Optimization Benchmarks 2016-01-25 14:43:11 Post No. 7809740

[Report] Image search: [iqdb] [SauceNao] [Google]

Small Combinatoric Optimization Benchmarks 2016-01-25 14:43:11 Post No. 7809740

[Report] Image search: [iqdb] [SauceNao] [Google]

Hello, /sci/!

I'm an undergraduate in computer science (hopefully) going on to graduate study next year. Since my program is research-oriented, and also because I can't always take classes in subjects I'm interested in, I spend a lot of free time trying my hand at traditionally 'hard' problems in order to get practice tackling unanswered questions (or at least questions whose answers haven't yet been proven beyond doubt).

I've recently come up with a fast heuristic (I'm calling it so because I don't yet have the grounds to prove or disprove) for a problem considered hard even to approximate in polynomial time (discovering the largest clique in an arbitrary graph).

While on one hand I'm aware that my procedure likely can be shown to be flawed by implementing it by hand and testing it on large graphs, I would prefer to do so first on smaller examples I can investigate manually in order to better understand the shortcomings of my approach, possibly improve it to generate a better heuristic, and more generally gain experience at generating counterexamples by inspection in this domain of problem.

So far, I've been able to verify my approach on small graphs I can come up with by hand, as well as benchmark classes I'm aware of which lend themselves to being drawn at a small scale (I've tried the Keller variant of DIMACS benchmark graphs, but even a 3-Keller graph is somewhat cumbersome to manipulate with pen and paper). My point in making this thread is to ask if any of you are aware of classes of graphs in which it is proven (or at least thought) that finding the largest clique quickly (in polynomial or pseudo-polynomial time) is hard, while also lending themselves to being generated in a small (<= 25?) number nodes.

Thanks for any direction you may be able to offer!

>>

Also, P =? NP general, if that sparks anybody's interest.

To those better versed than I: what is the current state of approximability of graph-related NP-hard problems? I read a paper stating that there's a proven maximum bound on the approximation factor for any maximum clique algorithm of n^(1/3) (unless P = NP), but I'm not sure if there's been any change since that point.

>>

>>7809740

>hard even to approximate in polynomial time

Stop your research immediately before you do something that many more people will regret. The government is not to be trusted in any whit.

>>

>>7809785

I highly doubt anything I do as an undergraduate toying with concepts will result in anything earth-shattering. But I suppose I should thank you for thinking that it might!

>>

>>7809831

Curiosity and hard work can lead to interesting and important results no matter what stage you are at in your academic career. CS, being a relatively young field, still holds many opportunities for discovery for a motivated researcher. Keep up the good work...

>>

>>7809740

>I'm an undergraduate in computer science (hopefully) going on to graduate study next year

You've made a horrible mistake.

>>

>>7810260

I personally don't believe I've made a mistake; I've enjoyed and learned a lot from my education so far.

>>

>>7810274

don't feed the trolls...

>>

>>7810228

Thanks!

>>7810290

... and, yeah, that's probably for the best.

In any case, would you be aware of some instances in which it would be hard to find a clique in a graph? I was thinking of coming up with a scheme whereby I could generate short (a few clauses and a few variables) SAT expressions that have exactly one satisfying assignment and then use the graph as a benchmark.

>>

>>7810329

just to specify, the graph resulting from reducing SAT for that expression to the clique problem*

>>

>>7810346

Not sure off of the top of my head where to point you to find a specific example of this, but I'll guarantee they are out there. It's been a few years since I played with this stuff. I do like your idea of creating your own example, at least to start with. That will be educational in itself.

>>

>>

>>7810329

>would you be aware of some instances in which it would be hard to find a clique in a graph

Obviously a graph with many 'just' sub-optimal cliques would be a pain in the ass to deal with. Generate a maximal clique and then many 'just' smaller clique (max-1, max-2, etc) and glue them randomly together or partially overlap them.

>>

>>7810398

Why are you so butthurt about a guy enjoying his chosen field? Sounds like you are bitter about something.

>>

>>7810464

Are you familiar with Hamming graphs? They seem like a principled approach at what you mention, but they too suffer from the issue of not being easily generated in a small number of nodes. https://en.wikipedia.org/wiki/Hamming_graph

Most of my self-generated instances have been surrounding many sub-optimal (and optimal) cliques 'glued' and transposed on top of one another. They have been the more challenging instances; I'll say that.

>>7810398

I'm friends with quite a few people in other STEM disciplines (in fact, we share a lot of classes). I even have pure mathematics friends who share interests with me.

Lucky, my undergraduate institution is more geared towards preparing its students for graduate-level research/coursework; we actually take the same classes as the PhD and Master's students.

>>

>>7810500

This. Even if computer science were utterly useless, it's definitely a field that can produce a living, and there's nothing wrong with somebody having a genuine interest in what he or she studies.

Given how practical and pervasive computer science is now, though, I really don't see a problem with somebody enjoying and pursuing it. The problem given in the OP is a major one in the intersection of computer science and mathematics whose answer relates to one of the biggest mathematical problems we know of. More power to anybody wanting to pursue computer science for genuine reasons, I'd say.

Thread images: 1

Thread DB ID: 464563

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's