Popular matchings with variable item copies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. 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 G = (A U 3, E) where A is the set of people and 2 is the set of items, and a list < c(1),...., c(vertical bar B vertical bar)> denoting upper bounds on the number of copies of each item, does there exist < x(1),...., x(vertical bar B vertical bar)> such that for each i, having x(i) copies of the i-th item, where 1 <= xi <= c(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. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. (C) 2011 Elsevier B.V. All rights reserved.

Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing

In this paper we address a scheduling problem for minimising total weighted tardiness. The motivation for the paper comes from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real life scenarios like unequal release times, incompatible job families, non-identical job sizes and allowance for job splitting have been considered. A mathematical model taking into account dynamic starting conditions has been developed. Due to the NP-hard nature of the problem, a few heuristic algorithms have been proposed. The performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small size problem instances, and (b) in comparison with `estimated optimal solution' for large size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal solutions (that is, statistically estimated one) in very reasonable computational time.

An Efficient Simulated Annealing With a Valid Solution Mechanism For TDMA Brodcast Scheduling problem

This paper presents an efficient Simulated Annealing with valid solution mechanism for finding an optimum conflict-free transmission schedule for a broadcast radio network. This is known as a Broadcast Scheduling Problem (BSP) and shown as an NP-complete problem, in earlier studies. Because of this NP-complete nature, earlier studies used genetic algorithms, mean field annealing, neural networks, factor graph and sum product algorithm, and sequential vertex coloring algorithm to obtain the solution. In our study, a valid solution mechanism is included in simulated annealing. Because of this inclusion, we are able to achieve better results even for networks with 100 nodes and 300 links. The results obtained using our methodology is compared with all the other earlier solution methods.

Study of the reaction between 1,2,3-trihydroxybenzene and 8-hydroxyquinoline in the solid state

1.2,3-Trihydroxybenzene (THB) reacts with 8-hydroxyquinoline (8HQ) in the solid state forming an orange-coloured charge transfer complex THB* (8HQ)(2). When the reaction was carried out in a petri dish, or when the vapours of 8HQ were allowed to react with solid THB (gravimetric study), the reaction product separated out as good quality, shiny single crystals. X-Ray diffraction studies on single crystals showed that they belong to the orthorhombic system with a = 15.408(1), b = 16.276(1), c = 7.825(1) Angstrom, Z = 4, D-x = 1.413 g cm(-3) and space group Pnaa. From the crystallographic evidence it has been found that the proton of the middle OH group of THB is transferred to the N atom of 8HQ. This accounts for the observed colour change. Kinetic studies on the solid state reaction showed that the 8HQ molecules diffuse towards THB, and the lateral diffusion occurs through surface migration, grain boundary diffusion and vapour phase diffusion. Gravimetric studies of the reaction between solid THB and 8HQ vapour showed that the diffusion of 8HQ molecules into the crystal lattice of THB has a higher energy of activation than that observed when the reactants are in contact. The nature of the crystal packing in the reaction product indicates diffusion of 8HQ molecules into the crystal lattice of THB along the c-axis, to occupy the cavities present between the THB molecules in the unit cell.

Deformation behaviour of commercially pure titanium at extreme strain rates

The evolution of microstructure and texture during room temperature compression of commercially pure Ti with four different initial orientations were studied under quasi-static and dynamic loading conditions. At a low strain rate (epsilon)over dot = 3 x 10(-4) s(-1) the different initial textures yielded the same end texture, despite different microstructural evolution in terms of twin boundaries. High strain rate deformation at (epsilon)over dot = 1.5 x 10(3) s(-1) was characterized by extensive twinning and evolution of a texture that was similar to that at low strain rate with minor differences. However, there was a significant difference in the strength of the texture for different orientations that was absent for low strain rate deformed samples at high strain rate. A viscoplastic self-consistent model with a secant approach was used to corroborate the experimental results by simulation. (C) 2011 Published by Elsevier Ltd. on behalf of Acta Materialia Inc.

Popular mixed matchings

We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be more popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if phi(M, T) >= phi(T, M) for all matchings T, where phi(X, Y) is the number of applicants that prefer X to Y. Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function phi that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if phi(P, Q) >= phi(Q, P) for all mixed matchings Q. We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem. (C) 2010 Elsevier B.V. All rights reserved.

Delay constrained optimal relay placement for planned wireless sensor networks

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

Formation of Ce1-xPdxO2-delta solid solution in combustion-synthesized Pd/CeO2 catalyst: XRD, XPS, and EXAFS investigation

Pd/CeO2 (1 at. %) prepared by the solution-combustion method shows a higher catalytic activity for CO oxidation and NO reduction than Pd metal, PdO, and Pd dispersed over CeO2 by the conventional method. To understand the higher catalytic properties, the structure of 1 at. % Pd/CeO2 catalyst material has been investigated by X-ray diffraction (XRD), X-ray photoelectron spectroscopy (XPS), and extended X-ray absorption fine structure (EXAFS) spectroscopy. The diffraction lines corresponding to Pd or PdO are not observed in the high-resolution XRD pattern of 1 at. % Pd/CeO2. The structure of 1 at. % Pd/CeO2 could be refined for the composition of Ce0.99Pd0.01O1.90 in the fluorite structure with 5% oxide ion vacancy. Pd(3d) peaks in the XPS in I at. % Pd/CeO2 are shifted by 3 eV indicating that Pd is in a highly ionic +2 state. EXAFS studies show the average coordination number of 3 around Pd2+ ion in the first shell of 1 at. % Pd/CeO2 at a distance of 2.02 Angstrom, instead of 4 as in PdO. The second shell at 2.72 Angstrom is due to Pd-Pd correlation which is larger than 2.69 Angstrom in PdO. The third shell at 3.31 Angstrom having 7 coordination is absent either in Pd metal or PdO, which can be attributed to -Pd2+-Ce4+- correlation. Thus, 1 at. % Pd/CeO2 forms the Ce1-xPdxO2-delta type of solid solution having -Pd2+-O-2-Ce4+- kinds of linkages.

Structural investigation of combustion synthesized Cu/CeO2 catalysts by EXAFS and other physical techniques: Formation of a Ce1-xCuxO2-delta solid solution

The structure and chemical environment of Cu in Cu/CeO2 catalysts synthesized by the solution combustion method have been investigated by X-ray diffraction (XRD), transmission electron microscopy (TEM), electron paramagnetic resonance (EPR) spectroscopy, X-ray photoelectron spectroscopy (XPS), cyclic voltammetry (CV), and extended X-ray fine structure (EXAFS) spectroscopy. High-resolution XRD studies of 3 and 5 atom % Cu/CeO2 do not show CuO lines in their respective patterns. The structure could be refined for the composition Ce1-xCuxO2-delta (x = 0.03 and 0.05; delta similar to 0.13 and 0.16) in the fluorite structure with 5-8% oxide ion vacancy. High-resolution TEM did not show CuO particles in 5 atom % Cu/CeO2. EPR as well as XPS studies confirm the presence of Cu2+ species in the CeO2 matrix. Redox potentials of Cu species in the CeO2 matrix are lower than those in CuO. EXAFS investigations of these catalysts show an average coordination number of 3 around the Cu2+ ion in the first shell at a distance of 1.96 Angstrom, indicating the O2- ion vacancy around the Cu2+ ion. The Cu-O bond length also decreases compared to that in CuO. The second and third shell around the Cu2+ ion in the catalysts are attributed to -Cu2+-O2--Cu2+ - at 2.92 Angstrom and -Cu2+-O2--Ce4+- at the distance of 3.15 Angstrom, respectively. The present results provide direct evidence for the formation of a Ce1-xCuxO2-delta type of solid solution phase having -square-Cu2+-O-Ce4+- kind of linkages.

The restriction mapping problem revisited

In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied techniques for restriction mapping. While double digest is NP-complete, there is no known polynomial-time algorithm for partial digest. Another disadvantage of the above techniques is that there can be multiple solutions for reconstruction. In this paper, we study a simple technique called labeled partial digest for restriction mapping. We give a fast polynomial time (O(n(2) log n) worst-case) algorithm for finding all the n sites of a DNA molecule using this technique. An important advantage of the algorithm is the unique reconstruction of the DNA molecule from the digest. The technique is also robust in handling errors in fragment lengths which arises in the laboratory. We give a robust O(n(4)) worst-case algorithm that can provably tolerate an absolute error of O(Delta/n) (where Delta is the minimum inter-site distance), while giving a unique reconstruction. We test our theoretical results by simulating the performance of the algorithm on a real DNA molecule. Motivated by the similarity to the labeled partial digest problem, we address a related problem of interest-the de novo peptide sequencing problem (ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 389-398), which arises in the reconstruction of the peptide sequence of a protein molecule. We give a simple and efficient algorithm for the problem without using dynamic programming. The algorithm runs in time O(k log k), where k is the number of ions and is an improvement over the algorithm in Chen et al. (C) 2002 Elsevier Science (USA). All rights reserved.

Evolution of crystallographic texture during deformation of submicron grain size titanium

Evolution of deformation texture in commercially pure titanium with submicron grain size (SMG) was studied using x-ray diffraction (XRD) and electron back scatter diffraction (EBSD) methods. The material was deformed by rolling at room temperature. The deformation mechanism was found to be slip dominated with a pyramidal slip system facilitating plastic deformation. No evidence of tensile or compressive twinning was detected, as generally seen in the case of titanium with conventional microcrystalline grain size. The absence of twinning and the propensity of the pyramidal slip system in the SMG Ti is attributed to the lack of coordinated motion of zonal partial dislocations that leads to twinning.

Low temperature synthesis, structure and properties of alkali-doped La2NiO4, LaNiO3 and LaNi0.85Cu0.15O3 from alkali hydroxide fluxes

We report a low-temperature synthesis of La1.95Na0.05NiO4 from NaOH flux, La0.97K0.03NiO3 and La0.95K0.05Ni0.85Cu0.15O3 phases from KOH flux at 400 degreesC. Alkali-doped LaNiO3 can be prepared in KOH, but not in NaOH flux and La2NiO4 can be prepared in NaOH, but not in KOH flux. The flux-grown oxides were characterized by powder X-ray Rietveld profile analysis and electron microscopy. Sodium doped La2NiO4 crystallizes in orthorhombic structure and potassium doped LaNiO3-phases crystallizes in rhombohedral structure. La1.95Na0.05NiO4 is weakly paramagnetic and semiconducting while La0.97K0.03NiO3 and La0.95K0.05Ni0.85Cu0.15O3 show Pauli paramagnetic and metallic behavior. (C) 2002 Editions scientifiques et medicales Elsevier SAS. All rights reserved.

Bounded Unpopularity Matchings

We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching M is popular if there is no matching M' such that more people prefer M' to M than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied by Abraham et al. (SIAM J. Comput. 37(4):1030-1045, 2007). If there is no popular matching, a reasonable substitute is a matching whose unpopularity is bounded. We consider two measures of unpopularity-unpopularity factor denoted by u(M) and unpopularity margin denoted by g(M). McCutchen recently showed that computing a matching M with the minimum value of u(M) or g(M) is NP-hard, and that if G does not admit a popular matching, then we have u(M) >= 2 for all matchings M in G. Here we show that a matching M that achieves u(M) = 2 can be computed in O(m root n) time (where m is the number of edges in G and n is the number of nodes) provided a certain graph H admits a matching that matches all people. We also describe a sequence of graphs: H = H(2), H(3), ... , H(k) such that if H(k) admits a matching that matches all people, then we can compute in O(km root n) time a matching M such that u(M) <= k - 1 and g(M) <= n(1 - 2/k). Simulation results suggest that our algorithm finds a matching with low unpopularity in random instances.

Determining Top K Nodes in Social Networks using the Shapley Value

In this paper, we consider the problem of selecting, for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the social network. This problem is relevant in many settings such as analysis of co-authorship networks, diffusion of information, viral marketing, etc. However, in most situations, this problem turns out to be NP-hard. The existing approaches for solving this problem are based on approximation algorithms and assume that the objective function is sub-modular. In this paper, we propose a novel and intuitive algorithm based on the Shapley value, for efficiently computing an approximate solution to this problem. Our proposed algorithm does not use the sub-modularity of the underlying objective function and hence it is a general approach. We demonstrate the efficacy of the algorithm using a co-authorship data set from e-print arXiv (www.arxiv.org), having 8361 authors.