Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Kodric, Bojana"'
Autor:
Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan, Kociumaka, Tomasz, Kodric, Bojana, Policriti, Alberto, Prezza, Nicola
Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA 2021 and JACM 2023) as a powerful tool to index finite state automata, with applications to regular expression matching. They generalize Wheeler orders (Gagie et al., Theoreti
Externí odkaz:
http://arxiv.org/abs/2410.04771
Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i.e. a partition of agents into coaliti
Externí odkaz:
http://arxiv.org/abs/2311.11101
Autor:
Becker, Ruben, Canton, Matteo, Cenzato, Davide, Kim, Sung-Hwan, Kodric, Bojana, Prezza, Nicola
We initiate the study of sub-linear sketching and streaming techniques for estimating the output size of common dictionary compressors such as Lempel-Ziv '77, the run-length Burrows-Wheeler transform, and grammar compression. To this end, we focus on
Externí odkaz:
http://arxiv.org/abs/2310.17980
Autor:
Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan, Kodric, Bojana, Maso, Riccardo, Prezza, Nicola
Wheeler automata were introduced in 2017 as a tool to generalize existing indexing and compression techniques based on the Burrows-Wheeler transform. Intuitively, an automaton is said to be Wheeler if there exists a total order on its states reflecti
Externí odkaz:
http://arxiv.org/abs/2307.07267
Autor:
Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan, Kodric, Bojana, Policriti, Alberto, Prezza, Nicola
A Wheeler automaton is a finite state automaton whose states admit a total Wheeler order, reflecting the co-lexicographic order of the strings labeling source-to-node paths. A Wheeler language is a regular language admitting an accepting Wheeler auto
Externí odkaz:
http://arxiv.org/abs/2306.04737
Autor:
Becker, Ruben, Cáceres, Manuel, Cenzato, Davide, Kim, Sung-Hwan, Kodric, Bojana, Olivares, Francisco, Prezza, Nicola
Wheeler nondeterministic finite automata (WNFAs) were introduced as a generalization of prefix sorting from strings to labeled graphs. WNFAs admit optimal solutions to classic hard problems on labeled graphs and languages. The problem of deciding whe
Externí odkaz:
http://arxiv.org/abs/2305.05129
We study PAC learnability and PAC stabilizability of Hedonic Games (HGs), i.e., efficiently inferring preferences or core-stable partitions from samples. We first expand the known learnability/stabilizability landscape for some of the most prominent
Externí odkaz:
http://arxiv.org/abs/2301.13756
Autor:
Becker, Ruben, Casteigts, Arnaud, Crescenzi, Pierluigi, Kodric, Bojana, Renken, Malte, Raskin, Michael, Zamaraev, Viktor
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erd\H{o}s-R\'enyi random graph model. The proposed model is obtained by randomly
Externí odkaz:
http://arxiv.org/abs/2205.14888
Autor:
Kesselheim, Thomas, Kodric, Bojana
We study the price of anarchy of mechanisms in the presence of risk-averse agents. Previous work has focused on agents with quasilinear utilities, possibly with a budget. Our model subsumes this as a special case but also captures that agents might b
Externí odkaz:
http://arxiv.org/abs/1804.09468
Autor:
Hoefer, Martin, Kodric, Bojana
The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision m
Externí odkaz:
http://arxiv.org/abs/1702.01290