Small Combinatoric Optimization Benchmarks

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.

>>7810274
>learned a lot

A bit, you've enjoyed and learned a bit from your education. The course load in CS is a fraction what you see in other STEM disciplines and a far cry from graduate course work.

>>7810290
>trolls

It's not trolling, its a warning to others not the make the same mistake.

>>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.