IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

In this paper we consider the problem of computing an "optimal" popular matching. We assume that our input instance G = (A ∪ P, E1 over(∪, ̇) ⋯ over(∪, ̇) Er) admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O (n2 + m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants. © 2009 Elsevier B.V. All rights reserved.

Department of Computer Science and Engineering

World University root node

Fulltext

Discrete Applied Mathematics

Optimal popular matchings

We consider the problem of matching people to jobs, where each person ranks a subset of jobs in an order of preference, possibly involving ties. There are several notions of optimality about how to best match each person to a job; in particular, popularity is a natural and appealing notion of optimality. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph where is the set of people and is the set of jobs, and a list denoting upper bounds on the capacities of each job, does there exist such that setting the capacity of i-th job to x i , where 1≤x i ≤c i , for each i, enables the resulting graph to admit a popular matching. In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c i is 1 or 2. © 2009 Springer-Verlag Berlin Heidelberg.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Popular matchings with variable job capacities

We use linear stability analysis to show that an isotropic phase of elongated particles with dipolar flow fields can develop nematic order as a result of their activity. We argue that ordering is favoured if the particles are flow-aligning and is strongest if the wavevector of the order perturbation is neither parallel nor perpendicular to the nematic director. Numerical solutions of the hydrodynamic equations of motion of an active nematic confirm the results. The instability is contrasted to the well-known hydrodynamic instability of an ordered active nematic.