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
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.
Meeting Information
Join Zoom Meeting ID:934 6880 2063
https://gmu.zoom.us/j/93468802063
