We introduce the classified stable matching problem, a problem motivated by academic hiring. Suppose that a number of institutes are hiring faculty members from a pool of applicants. Both institutes and applicants have preferences over the other side. An institute classifies the applicants based on their research areas (or any other criterion), and, for each class, it sets a lower bound and an upper bound on the number of applicants it would hire in that class. The objective is to find a stable matching from which no group of participants has reason to deviate. Moreover, the matching should respect the upper lower bounds of the classes. In the first part of the paper, we study classified stable matching problems whose classifications belong to a fixed set of order types.'' We show that if the set consists entirely of downward forests, there is a polynomial-time algorithm; otherwise, it is NP-complete to decide the existence of a stable matching. In the second part, we investigate the problem using a polyhedral approach. Suppose that all classifications are laminar families and there is no lower bound. We propose a set of linear inequalities to describe stable matching polytope and prove that it is integral. This integrality allows us to find various optimal stable matchings using Ellipsoid algorithm. A further ramification of our result is the description of the stable matching polytope for the many-to-many (unclassified) stable matching problem. This answers an open question posed by Sethuraman, Teo and Qian.
Abraham, Irving and Manlove introduced the student-project allocation problem @cite_2 . It can be shown that in , if all classifications are just partitions over the applicants and there is no lower bound, our problem is equivalent to a special case of their problem. They posed the open question whether there is a polynomial time algorithm for their problem if there is lower bound on the projects (classes). Our result in Section 2 gives a partial positive answer.
@cite_2
2012500540
Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a useful tool to design deterministic and randomized approximation algorithms. The mechanism design version of the scheduling problem was introduced by Nisan and Ronen. In this article, we consider the mechanism design version of the fractional variant of this problem. We give lower bounds for any fractional truthful mechanism. Our lower bounds also hold for any (randomized) mechanism for the integral case. In the positive direction, we propose a truthful mechanism that achieves approximation 3 2 for 2 machines, matching the lower bound. This is the first new tight bound on the approximation ratio of this problem, after the tight bound of 2, for 2 machines, obtained by Nisan and Ronen. For n machines, our mechanism achieves an approximation ratio of n+1 2. Motivated by the fact that all the known deterministic and randomized mechanisms for the problem assign each task independently from the others, we focus on an interesting subclass of allocation algorithms, the task-independent algorithms. We give a lower bound of n+1 2, that holds for every (not only monotone) allocation algorithm that takes independent decisions. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms. We study the following online preemptive scheduling problem: given a set of jobs with release times, deadlines, processing times and weights, schedule them so as to maximize the total value obtained. Unlike traditional scheduling problems, partially completed jobs can get partial values proportional to their amounts processed. Recently gave improved lower and upper bounds (1.236, 1.8) on the competitive ratio for this problem, the upper bound being achieved by using timesharing to simulate two equal-speed processors. In this paper we (1) give a new algorithm MIXED-k with competitive ratio 1 (1 − (k (k + 1)) k ) which approaches e (e−1) ≈ 1.582 when k →∞ , by using timesharing to simulate k equal-speed processors; (2) give an equivalent but much more practical algorithm MIX, which is e (e − 1)-competitive (independent of k), by timesharing the processor with different speeds (depending on the job weights), and use its interesting properties to devise an efficient implementation; (3) improve the lower bound to 1.25 by showing an identical lower bound for randomized algorithms; and (4) prove a lower bound of 1.618 on the competitive ratio when timesharing is not allowed, thus answering an open problem raised by Chang and Yap, showing that timesharing provably helps in giving better algorithms for this problem. We study the problem of computing maximin share allocations, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of an agent is the best she can guarantee to herself, if she is allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find a partition, where each agent is guaranteed her maximin share. Such allocations do not always exist, hence we resort to approximation algorithms. Our main result is a 2 3-approximation that runs in polynomial time for any number of agents and goods. This improves upon the algorithm of Procaccia and Wang (2014), which is also a 2 3-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of the algorithm in Procaccia and Wang (2014), exploiting the construction of carefully selected matchings in a bipartite graph representation of the problem. Furthermore, motivated by the apparent difficulty in establishing lower bounds, we undertake a probabilistic analysis. We prove that in randomly generated instances, maximin share allocations exist with high probability. This can be seen as a justification of previously reported experimental evidence. Finally, we provide further positive results for two special cases arising from previous works. The first is the intriguing case of three agents, where we provide an improved 7 8-approximation. The second case is when all item values belong to 0, 1, 2 , where we obtain an exact algorithm. We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. As a special case, this gives a new proof for the time-space lower bound for parity learning [R16]. Our result is stated in terms of the norm of the matrix that corresponds to the learning problem. Let X, A be two finite sets. Let M: A &#x00D7; X -1,1 be a matrix. The matrix M corresponds to the following learning problem: An unknown element x &#x220A; X was chosen uniformly at random. A learner tries to learn x from a stream of samples, (a_1, b_1), (a_2, b_2)..., where for every i, a_i &#x220A; A is chosen uniformly at random and b_i = M(a_i,x). Let be the largest singular value of M and note that always &#x2264; |A|^ 1 2 &#x22C5; |X|^ 1 2 . We show that if &#x2264; |A|^ 1 2 &#x22C5; |X|^ 1 2 - &#x2265;ilon, then any learning algorithm for the corresponding learning problem requires either a memory of size quadratic in &#x2265;ilon n or number of samples exponential in &#x2265;ilon n, where n = |X|.As a special case, this gives a new proof for the memorysamples lower bound for parity learning [14].