http://https://youtu.be/JDA1fADYtSI
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
Abstract
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.