Discrete mathematics and graph theory · Maths EE idea · Ambitious

How good is a quick tour?

A research question to start from

How close to optimal are the nearest-neighbour and tree-doubling heuristics for the travelling salesperson problem, and what guarantees can be proved?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

Approximation guarantees are provable statements about algorithms; ideal for analysis and evaluation.

Mathematics you would need

Hamiltonian cycles
Triangle inequality
Minimum spanning trees
Lower and upper bounds

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove the factor-2 guarantee for tree doubling with the triangle inequality.
Construct examples where nearest neighbour does badly.
Compare heuristics on networks you build.

Scope and difficulty

Ambitious. Ambitious.

Pitfalls

Algorithm runs without proofs.
Ignoring the triangle inequality.

Where to start reading

Search a library catalogue or a university's open lecture notes for: TSP approximation 2-approximation MST triangle inequality; nearest neighbour worst case. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.