frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

K Set Cover Solving Algorithm

3•a_florea•2d ago
Hello everyone, I’m looking for advice. I’ve been studying the k set cover problem (and related problems) for over a year, I’ve noticed that there is no known algorithm that can solve this problem for every instance optimal and any algorithm that does so, just takes to much time if the problem is of certain size. I think there is a big misconception about the nature of this problem because there is an easy and fast way to just solve all of them within reasonable amount of time and I’ve spent a whole year just proving that it works for any problem of this category the same boring way. Now however I have I have a very efficient algorithm (on paper), I know this could be extremely useful, but Im just lacking the right help and advices, what should I do with it?

wunderpus@mail.com

Thanks guys

Comments

ecesena•2d ago
Publish it on arxiv?
davidanekstein•1d ago
Isn’t this an NP hard problem?
gus_massa•1d ago
This problem? https://en.wikipedia.org/wiki/Set_cover_problem

> Now however I have a very efficient algorithm (on paper)

Why not code?

> I’ve spent a whole year just proving that it works for any problem of this category the same boring way

I don't know enough about this problem, but it's common that most examples are easy and can be solved with an efficient heuristic, but there are an infinite family of rare corner cases were the heuristic fails and the solution is very slow.

[IIRC, for the traveling salesman problem, the hard cases are when the distances are just small differences 1.0001912876; 1.0010221987; 1.01002112; 1.030152322; 1.01026; 1.0102131287; ... or something like that (this are just numbers I typed randomly).]

Ask HN: How are you acquiring your first hundred users?

473•amanchanda•17h ago•299 comments

Ask HN: How do you store the knowledge gained in a day?

32•dennisy•7h ago•58 comments

Good luck to everyone applying for YC summer 2925 batch

3•byoung2•2h ago•2 comments

Ask HN: Economists, what's your opinion on US tariffs?

6•pinkmuffinere•3h ago•1 comments

FlyLoop – AI Agent for Scheduling Meetings and Managing Your Calendar

16•localbuilder•12h ago•2 comments

Ask HN: Cursor or Windsurf?

291•skarat•1d ago•373 comments

New AI Chatbot Apps

2•bennyv1211•6h ago•0 comments

Ask HN: How do you like the Framework matte screen?

4•christophilus•9h ago•1 comments

Which AI Agent is your favorite?

2•jeyzolo•7h ago•4 comments

Ask HN: How did you fund your early stage hardware startup?

2•mrtb•9h ago•0 comments

Ask HN: Is Slack Down?

68•abatilo•1d ago•29 comments

Ask HN: What are good high-information density UIs (screenshots, apps, sites)?

522•troupo•5d ago•370 comments

Ask HN: I burnt out, quit my job – any advice on moving to freelance/consulting?

8•gardennoise•1d ago•13 comments

Ask HN: Not sure about the future of tech

15•xblpob•1d ago•13 comments

Ask HN: Should You Include a Certificate in a SAML AuthnRequest?

5•andy89•1d ago•2 comments

Ask HN: Did GitHub UI become unbearably slow?

10•zaphodias•1d ago•8 comments

Ask HN: How much better are AI IDEs vs. copy pasting into chat apps?

137•lopatin•5d ago•136 comments

Ask HN: Any recommendations for a portable music player

5•laserstrahl•1d ago•5 comments

Ask HN: Where to get used hardware cheap?

4•laserstrahl•1d ago•7 comments

Ask HN: Do You Prepare for Job Interviews? If So, How?

5•dovab•1d ago•10 comments

Ask HN: Gemini Reliability Degrading?

7•martinald•2d ago•2 comments

Ask HN: Are LLMs useful or harmful when learning to program?

11•dominicq•2d ago•20 comments

Why is it so hard to find founders to bounce off ideas in city you are visiting?

10•nickevante•2d ago•29 comments

Image to 3D

2•theankur7•1d ago•3 comments

Ask HN: Is big tech still more stable?

9•ronbenton•2d ago•13 comments

Ask HN: What is the worst communications tool you've ever used?

11•logicallee•3d ago•33 comments

Ask HN: Anyone using Chrome ext with AI for daily copywriting/social media?

7•refinedea•2d ago•3 comments

LLM Botnet: Are companies using botnets to scrape content?

3•flyriver•2d ago•3 comments

Ask HN: RAG or shared memory for task planning across physical agents?

11•mbbah•4d ago•2 comments

Ask HN: Fictional business books like The Goal

11•jimnotgym•3d ago•7 comments