Here are some tentative topics.

You will get bonus point (up to 5pts) if you can solve an interesting open-ended problem.

Of course, you are allowed to use AI to help you.

If you are not sure if the problem you are trying to solve is reasonable problem to study, you can contact me.

Send me an email ( lapordge@gmail.com ) or wechat msg and schedule a meeting with me.



Here are some tips if you have no research experience.
You can do the following:

(1) First try to find the history of the problem you are interested in, what is the state-of-the-art algorithm for this problem. Google or ask LLM (sometimes LLM hallucinates and you need to double check with google).

(2) For many problems, there are prior results on upper bounds and lower bounds. Read the most recent paper on this topic, in particular the related work section (which may contain the history of the problem). Ask yourself whether these bounds are still improvable.
If the best result for a problem is already optimal, then perhaps there is not much room to improve on it.

(3) Take a quick look at the paper and see if you have enough math/theory/algorithm background to understand the paper. If you find several terminologies that you are not familiar with, perhaps you should learn some background knowledge first.

(4) You may create some interesting and meaningful extensions of existing problem and try to solve the extensions.

(5) If you have difficulty solving some problem, you may try to solve some nontrivial special cases of the problem first.

(6) Of course, you are allowed to use AI to help you in solving the problem and writing the paper. But you should understand the proof provided by AI and polish it so that human reviewers can understand it.




You need to write a research report for your project.
There is no restriction on the length of the report.
But the format should be the same as a formal research paper.
You need a title, an abstract, an introduction section in which you need to formally introduce your problem and provide proper motivation, a related work section which details all related and prior results on this topic. The report should be well polished, readable and self-contained for an undergrad student (e.g., you classmates)



Format requirement:
The report should be written in latex.

\documentclass[11pt]{article}
\usepackage{fullpage}

You should use bibtex for the reference.
\bibliography{references}
\bibliographystyle{plain}


Do not cheat! (otherwise you will get 0 for this part)

Do not
(1) copy & paste sentences/paragraphs from other places without proper citations.
(2) use your own report or papers etc. from previous semesters without much changes (but we allow you to write this report based on your previous work). But the main job must be done in this semester.
(3) violate other academic code of ethics

In general, you can ask chatGPT (or GPT 4 or other LLMs) as follows.



Now, you can either google or keep asking chatGPT. Sometimes, chatGPT hallucinates and you need google.



Project

New Results on a General Class of Minimum Norm Optimization Problems

Pursue the direction in the conclusion section of the above paper. In particular, improve the pseudo-polynomial time algorithm for min-norm shortest path to a poly-time algorithm (constant approximation).



Project
Stochastic optimization

If you like linear programming, approximation algorithm and probability, this might be a good problem to think about.

How to Probe for an Extreme Value

(1)Try to improve the problem of minimizing E[min], for the case where the support m=poly(n).
The best known approximation ratio is O(logloglog n), improve it to O(1).
Send me a note if you want to know the reference.

(2)Try to prove the above case is NP-Complete.

Approximation Algorithms for Stochastic Combinatorial Optimization Problems.

Study open question 1 (improve the 2-approximation for stochastic knapsack), open question 5 (a difficult open question, matroid secretary) in this survey.

There are several other interesting open problems in this domain.



Project

Read the following elegant paper and learn the famous Gittin's index.

On playing golf with two balls

and the first part of the following paper
Multi-token Markov Game with Switching Costs.

Simplify the analysis and improve the approximation ratio to a small constant (hopefully without using the doubling technique)


Project

Coreset

Coreset is an important concept in solving various problems in big data era.

A coreset is a small-sized subset that approximates the cost of all solutions of a very large dataset.

Read the following survey (upto section 3.1)

Practical coreset constructions for machine learning

Goal: obtain tight coreset bounds for Euclidean k-median (talk to me if you are interested in this topic and I will tell you more information)

(2026 notes: the problem has been solved recently by AI)



Project

Show the k-densest subgraph problem is NPC (or in P) on interval graphs.
(difficult. this is a long-standing open problem. 30 years. but i am not sure how many ppl studied it seriously).

See the NPC proof for chordal graphs:
D. G. Corneil and Y. Perl. Cluster and domination in perfect graphs. Discrete
Applied Mathematics, 9:27{39, 1984.


Probably an easier one
Design a PTAS for the k-densest subgraph problem for chordal graphs

Read the following paper for a simple constant factor approximation algorithm for chordal graphs.
Densest k-Subgraph Approximation on Intersection Graphs

and the following paper for a PTAS for interval graphs
PTAS for Densest k-Subgraph in Interval Graphs



Project

The Price of Stability for Network Design with Fair Cost Allocation. (See also the text book, local search chapter)

The price of stability for undirected broadcast network design with fair cost allocation is constant

An O({\log n\over \log\log n}) Upper Bound on the Price of Stability for Undirected Shapley Network Design Games, IPL 2009

Improve this old O(log/loglogn) bound. Can we use the technique of the 2nd paper?



Some more ambitious problems.
(The following problems are very difficult. Some of them have been open for many years. I don't suggest you to spend a lot of time solely on these problems if you have no research experience before. But it doesn't hurt to give a shot, read some related papers and get a sense why the problem is difficult.
Of course, you can write survey for these problems, which is no more difficult than writing survey for other problems.
But for each topic, there may be some intermediate goals or some closely related problems which may be more doable. You can contact me if you are very interested and want to know more.)

1. Prove that the matroid secretary problem admits a constant factor approximation (the current best bound is loglogn).

read this paper: A simple O(log log(rank))-competitive algorithm for the matroid secretary problem (2026 notes: the problem has been solved recently by AI)

2. Obtain optimal approximation ratio for facility location

A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem

(for certain parameter range, one can get optimal approximation ratio. talk to me and i will let you know more details)

Lower bound see: Greedy strikes back: Improved facility location algorithms. (2026 notes: the problem has been solved recently by AI)

3. Design an FPTAS for approximating the number of perfect matchings in a general graph (it is known how to do this for bipartite graphs)

(2026 notes: the problem has been solved recently by AI)

4. improve the 2-approximation ratio for unrelated machine scheduling (it would be interesting to obtain better-than-2 approximations even for some special cases)

5. Gilbert-Pollak Conjecture (fully resolving this conj may be difficult. There was a claimed proof by Du and Hwang. But later the proof was found incomplete. So the problem is still open. A more doable direction is to get a tighter upper bound. The current best bound is 0.82. The conjectured bound is sqrt(3)/2=0.866.)

6. Linear time deterministic algorithm for minimum spanning tree (a long standing open problem)

7. Design a strongly polynomial time algorithm for linear programming (a long standing open problem and a central open problem in linear programming)



classic references:

Approximation Algorithms
By Vijay V. Vazirani

The Design of Approximation Algorithms
By Williamson and Shmoys

Randomized Algorithms
Rajeev Motwani, Prabhakar Raghavan

Online Algorithms
Amos Fiat, Gerhard J. Woeginger

Computers and Intractability: A Guide to the Theory of NP-Completeness 
by Michael Garey and David S. Johnson.
This is a dictionary of NP-complete problems

Combinatorial optimization: polyhedra and efficiency
A dictionary of combinatorial optimization problems.