Implementation of Held-Karp lower bound for the TSP

Open

#347 opened on Aug 31, 2023 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty: 5/5
Estimated time: Over a week
Newbie friendliness: 25/100

Issue type: Feature
Clarity: Needs clarification
Activity status: Stale
Tech stack: cpp
Domain: backend

Research direction

Start by reviewing the linked OR-Tools one-tree lower-bound reference, the cited research paper, and Boost.Graph's existing MST interfaces. Determine the appropriate BGL API and scope for the Held-Karp lower bound; done means the feature is implemented with coverage for representative TSP graphs and its behavior is documented.

Written by the indexing model from the issue text.

Description

algorithm priority: low

The Held-Karp lower bound for the TSP is a good lower bound for the TSP and at a big picture, it attempts to approximate the TSP from below by trying to obtain trees where a large number of nodes have degree 2. It still continues to attract research interest in the OR community. See for e.g., https://ojmo.centre-mersenne.org/item/10.5802/ojmo.11.pdf a recent work on this.

Google OR-Tools seems to provide an interface for this. Please see https://developers.google.com/optimization/reference/graph/one_tree_lower_bound

It would be great if the BGL team considers implementing the same in its libraries. I use BGL for many MST algorithms and it is very efficient. The Held-Karp lower bound uses MST as a subproblem.

Thank you.

Dominant language: C++
Stars: 395
Forks: 239
Avg merge: 18h 50m
Merged PRs (30d): 20

Contributor guide

Open the contributing guide

First steps

Read the whole issue, then the project's contributing guide.
Comment on the issue to say you are picking it up — it saves two people doing the same work.
Fork the repository and make your change on a branch.
Open a pull request that references the issue number.

Similar issues

[Bug] NULL pointer dereference in llm_running_callback (NGZA-AX-LLM #3) Open

Difficulty 1/5 Under an hour Newbie friendliness 90/100

AXERA-TECH/ax-llm#77 · Opened Sep 22, 2026
resume() sends a second HTTP response (400) after a successful resume Open

Difficulty 1/5 Under an hour Newbie friendliness 90/100

games-on-whales/wolf#509 · Opened Sep 21, 2026
pn7160: reader goes permanently deaf — post-read IRQ-low check fails reads that succeeded Open

Difficulty 2/5 1-3 hours Newbie friendliness 74/100

esphome/esphome#19452 · Opened Sep 21, 2026
Eval bug: Ministral-3 tool-calls during reasoning are not processed Open

bug-unconfirmed

Difficulty 2/5 1-3 hours Newbie friendliness 76/100

ggml-org/llama.cpp#29248 · Opened Sep 21, 2026
run_tests.py fails on windows, but running tests individually works Open

Difficulty 2/5 1-3 hours Newbie friendliness 74/100

NVIDIA/cuda-samples#453 · Opened Sep 21, 2026

More C++ issues