Extracting Verb Sense Hierarchies from FrameNet
Ran Iwamoto, Kyoko Ohara
ICLC 2023
We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the Lnorm of the vector of machine-loads, for all 1 < p < ; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer Lnorms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys & Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].
Ran Iwamoto, Kyoko Ohara
ICLC 2023
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Hannah Kim, Celia Cintas, et al.
IJCAI 2023
Bing Zhang, Mikio Takeuchi, et al.
NAACL 2025