QSEC Quantum Computing Seminar Series: 10/27/2020

12 pm, October 27, 2020
Speaker: Professor Fei Li, GMU Department of Computer Science

Topic: Algorithmic Approaches to the MAX-CUT Problem

Location: Zoom

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 upcoming seminar on Tuesday October 27 will be given by Professor Fei Li of GMU Computer Science. Below is the abstract of the talk and meeting information:

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.

Meeting Information
Join Zoom Meeting ID:934 6880 2063