Warning: Table './church/sessions' is marked as crashed and last (automatic?) repair failed
query: SELECT sid FROM sessions WHERE sid = '1c4e5a4ap0pukibu6gdo7n1f76' in /var/www/church/includes/database.mysql.inc on line 121 Gruppo di Logica e Geometria della Cognizione
Venerdì 5 marzo 2021 alle ore 15:00, il dott. Chien-Chung Huang (CNRS / École Normale Supérieure PSL, Paris) presenterà il seminario di Logica e Informatica Teorica dal titolo: "Minimizing the Number of Unhappy Singles: Improved Approximation Algorithms for Stable Marriage".
Abstract:
We consider the problem of computing a large stable matching in a bipartite graph G = (A ? B, E) where each vertex u ? A ? B ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a,b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard. We design an algorithm to give a 1.4667-approximation for the special case where all ties of the preferences appear on the B-side. This algorithm is purely combinatorial and takes only linear time.
Per partecipare al Seminario cliccare sul seguente Link: https://bit.ly/3uPLhvf.
Warning: Can't find file: 'watchdog' (errno: 2)
query: INSERT INTO watchdog (uid, type, message, severity, link, location, referer, hostname, timestamp) VALUES (0, 'php', 'Table './church/sessions' is marked as crashed and last (automatic?) repair failed\nquery: SELECT sid FROM sessions WHERE sid = '1c4e5a4ap0pukibu6gdo7n1f76' in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/calendario/2021/03/5', '', '98.80.143.34', 1728489167) in /var/www/church/includes/database.mysql.inc on line 121
Warning: Can't find file: 'watchdog' (errno: 2)
query: INSERT INTO watchdog (uid, type, message, severity, link, location, referer, hostname, timestamp) VALUES (0, 'php', 'Table './church/sessions' is marked as crashed and last (automatic?) repair failed\nquery: INSERT INTO sessions (sid, uid, cache, hostname, session, timestamp) VALUES ('1c4e5a4ap0pukibu6gdo7n1f76', 0, 0, '98.80.143.34', 'calendar_year|i:2021;calendar_mon|i:3;', 1728489167) in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/calendario/2021/03/5', '', '98.80.143.34', 1728489167) in /var/www/church/includes/database.mysql.inc on line 121
