QSEC Quantum Computing Seminar Series: 10/27/2020, Algorithmic Approaches to the MAX-CUT Problem, by Fei Li of George Mason University

October 27, 2020 @ 12:00 pm – 1:00 pm

Event Record


QSEC’s quantum computing subgroup will organize and host a seminar series throughout the upcoming semester.  These events are free and open to the public. For any questions, contact qsec@gmu.edu.

The recorded seminar on Tuesday October 27 was given by Professor Fei Li of GMU Computer Science. Below is the abstract of the talk:

Speaker: Professor Fei Li, GMU Department of Computer Science

Title: Algorithmic Approaches to the MAX-CUT Problem


In this talk, I am going to present three approximation algorithms to deal with the NP-hard problem MAX-CUT. The first one is a 0.5-approximation randomized algorithm, which can be de-randomized to be a deterministic one with the same performance. The second approximation algorithm is also a randomized algorithm and it has an approximation ratio 0.878. The third algorithm is a quantum approximation optimization algorithm (QAOA) with an approximation ratio 0.6942 on 3-regular graphs. In this talk, I will compare these algorithmic approaches. I will also discuss the inapproximability and some of my thoughts on solving MAX-CUT.