5 papers · 1 filter
Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time
Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in…
The Complexity of Justified Representation with Additive Utilities
Carmel Baharav, Jakob de Raaij, Agnès Totschnig
We study the computational complexity of satisfying proportional representation -- in particular proportional, extended, and fully justified representation (PJR, EJR, and FJR) -- i…
Almost perfect graph classes
Cicely Henderson, Hidde Koerts, Taite LaGrange +4
A graph is perfect if for each induced subgraph of . In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem.…
Fair Division of Graphs: Beyond Traceability
Nicolas Bousquet, Frank Connor, Agnès Totschnig +1
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally al…
The Tiered Clinching Auction with Applications to Carbon Offset Markets
Tessa Davis, Agnès Totschnig, Adrian Vetta
Voluntary carbon offsetting is a strategy which has been pursued globally by corporations to reduce their effective carbon emissions. Carbon offset markets currently suffer from lo…