Campus Event Calendar
Event Entry
What and Who
Approximation Schemes for Subset Sum Ratio (Bachelor Thesis)
Jannik Kudla
Saarland University
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 18 December 2020
13:00
30 Minutes
Virtual talk
Virtual talk
Saarbrücken
Abstract
The Subset Sum Ratio problem asks for the following: Given a set A of n positive integers, find two non-empty disjoint subsets of A such that the ratio of their sums is as close to 1 as possible.
In this talk, we present two fully polynomial-time approximation schemes (FPTAS) for Subset Sum Ratio. They run in time near O(n^3 / eps) and O(n / eps^2), respectively, improving upon the previously known O(n^4 / eps) bound. The algorithms are based on dynamic programming and approximating (max, +)-convolutions in a divide and conquer fashion.
--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.
Contact
Sándor Kisfaludi-Bak
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.
Sándor Kisfaludi-Bak, 12/09/2020 13:20
Sándor Kisfaludi-Bak, 12/09/2020 13:20 -- Created document.
Sándor Kisfaludi-Bak, 12/09/2020 13:20 -- Created document.