17 papers · ranked by Valyu relevance
Michael Kearns, Yishay Mansour, Andrew Y. Ng
Assignment methods are at the heart of many algorithms for unsupervised learning and clustering - in particular, the well-known K -mean.! and E:z:pectation-Mazimi$ation (EM) algorithms. In this work, we study several different methods of assignment, including the "hard" assignments used by K-means and the "soft"…
Louis Mahon, Thomas Lukasiewicz
Online deep clustering refers to the joint use of a feature extraction network and a clustering model to assign cluster labels to each new data point or batch as it is processed. While faster and more versatile than offline methods, online clustering can easily reach the collapsed solution where the encoder maps all…
Sebástien Vérel, Sarah L. Thomson, Omar Rifki
The Quadratic Assignment Problem (QAP) is one of the major domains in the field of evolutionary computation, and more widely in combinatorial optimization. This paper studies the phase transition of the QAP, which can be described as a dramatic change in the problem's computational complexity and satisfiability, within…
Zeyuan Hu, C. Gregory Plaxton
In recent work on course allocation, Rodríguez and Manlove consider the complexity of finding a stable assignment under four notions of stability, including two coalitional notions. In one case, which they call pair-size stability, they show that a stable assignment always exists and they provide a polynomial-time…
Haris Aziz
We settle the complexity of computing a discrete CEEI (Competitive Equilibrium with Equal Incomes) assignment by showing it is strongly NP-hard. We then highlight a fairness notion (CEEI-FRAC) that is even stronger than CEEI for discrete assignments, is always Pareto optimal, and can be verified in polynomial time. We…
Kentaro Onda, Satoru Fukayama, Daisuke Saito, Nobuaki Minematsu
Discrete speech tokens obtained from self-supervised learning (SSL) models provide efficient data compression while maintaining strong performance, and have been widely used as intermediate representations in various tasks. However, discretization inevitably causes information loss, leading to degraded performance…
Salavat Ishbulatov
Personal and organizational planning systems maintain two records that drift apart: what was planned (a task's effort budget) and what was done (a logged action's duration and description). Existing systems bridge them with an exclusive, all-or-nothing link that strands genuinely related but unlinked effort and reports…
Ivan Stelmakh, Nihar B. Shah, Aarti Singh
We consider the problem of automated assignment of papers to reviewers in conference peer review, with a focus on fairness and statistical accuracy. Our fairness objective is to maximize the review quality of the most disadvantaged paper, in contrast to the commonly used objective of maximizing the total quality over…
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time (2 − δ)-approximation algorithm is known for the problem for constant δ > 0. This is true even for certain special cases, most notably the restricted assignment problem where each job has the same load on…
Sander Borst, Danish Kashaev
We study the online load balancing problem on unrelated machines, with the objective of minimizing the square of the ℓ 2 norm of the loads on the machines. The greedy algorithm of Awerbuch et al. (STOC'95) is optimal for deterministic algorithms and achieves a competitive ratio of 3 + 2 √ 2 ≈ 5.828, and an improved…
C. S. Karthik, Pasin Manurangsi
Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some ε > 0 such that given as input a k-CSP instance (for some constant k) over some constant sized alphabet, and two satisfying assignments ψs and ψt , it is PSPACE-hard to find a sequence…
Jason D. Hartline, Liren Shan, Yingkai Li, Yifan Wu
This paper develops a framework for the design of scoring rules to optimally incentivize an agent to exert a multi-dimensional effort. This framework is a generalization to strategic agents of the classical knapsack problem (cf. Briest, Krysta, and V¨ocking, 2005; Singer, 2010) and it is foundational to applying…
Jun He, Tianshi Chen
The hardness of fitness functions is an important research topic in the field of evolutionary computation. In theory, the study can help understanding the ability of evolutionary algorithms. In practice, the study may provide a guideline to the design of benchmarks. The aim of this paper is to answer the following…
Fu-Tao Hu, Moo Young Sohn
Let G = (V, E) be a graph. A subset D ⊆ V is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G, denoted by γ(G), is the smallest cardinality of a dominating set of G. The bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in…
Timo A. Nieminen, Serene H.-J. Choi, A. Rayner
Tiered assessment is a form of differentiated assessment [1] where students can attempt a series of assessment tasks, usually of increasing difficulty. All students attempt the lowest tier of the series, but the higher tiers are optional. The lowest tier should allow students to demonstrate sufficient foundational…
Sahasrajit Sarmasarkar, Harish K. Pillai
We consider the problem of job assignment where a master server aims to compute some tasks and is provided a few child servers to compute under a uniform straggling pattern where each server is equally likely to straggle. We distribute tasks to the servers so that the master is able to receive most of the tasks even if…
Jiale Chen, Jason D. Hartline, Onno Zoeter
This paper studies grading algorithms for randomized exams. In a randomized exam, each student is asked a small number of random questions from a large question bank. The predominant grading rule is simple averaging, i.e., calculating grades by averaging scores on the questions each student is asked, which is fair…