Improved algorithmic results for unsplittable stable allocation problems

The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is “stable” based on a set of underlying preference lists submitted by the jobs and machines. Building on the initial work of Dean et al. (The unsplittable stable marriage problem, 2006), we study a natural “unsplittable” variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem (McDermid and Manlove in J Comb Optim 19(3): 279–303, 2010). Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed in McDermid and Manlove (J Comb Optim 19(3): 279–303, McDermid and Manlove 2010), we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce “relaxed” unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.     

Keeping partners together: algorithmic results for the hospitals/residents problem with couples

The Hospitals/Residents problem with Couples (HRC) is a generalisation of the classical Hospitals/Residents problem (HR) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of hospitals (h _i ,h _j ). We consider a natural restriction of HRC in which the members of a couple have individual preference lists over hospitals, and the joint preference list of the couple is consistent with these individual lists in a precise sense. We give an appropriate stability definition and show that, in this context, the problem of deciding whether a stable matching exists is NP-complete, even if each resident’s preference list has length at most 3 and each hospital has capacity at most 2. However, with respect to classical (Gale-Shapley) stability, we give a linear-time algorithm to find a stable matching or report that none exists, regardless of the preference list lengths or the hospital capacities. Finally, for an alternative formulation of our restriction of HRC, which we call the Hospitals/Residents problem with Sizes (HRS), we give a linear-time algorithm that always finds a stable matching for the case that hospital preference lists are of length at most 2, and where hospital capacities can be arbitrary.     

Monotonicity of strong searching on digraphs

Given a digraph, suppose that some intruders hide on vertices or along edges of the digraph. We want to find the minimum number of searchers required to capture all the intruders hiding in the digraph. In this paper, we propose and study two digraph searching models: strong searching and mixed strong searching. In these two search models, searchers can move either from tail to head or from head to tail when they slide along edges, but intruders must follow the edge directions when they move along edges. We prove the monotonicity of each model respectively, and show that both searching problems are NP-complete. The research of B. Yang was supported in part by NSERC and MITACS.     

Parity and strong parity edge-colorings of graphs

A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. A parity edge-coloring (respectively, strong parity edge-coloring) is an edge-coloring in which there is no nontrivial parity path (respectively, open parity walk). The parity edge-chromatic number p(G) (respectively, strong parity edge-chromatic number $\widehat{p}(G)$ ) is the least number of colors in a parity edge-coloring (respectively, strong parity edge-coloring) of G. Notice that $\widehat{p}(G) \ge p(G) \ge \chi'(G) \ge \Delta(G)$ for any graph G. In this paper, we determine $\widehat{p}(G)$ and p(G) for some complete bipartite graphs and some products of graphs. For instance, we determine $\widehat{p}(K_{m,n})$ and p(K _m,n ) for m≤n with n≡0,?1,?2 (mod 2^?lg?m?).     

Psychological aspects of planning

This article examines the role of psychological variables in implementing planning models. Specifically, the impact of perceptual processes, cognitive ability, motivation, and values on planning models are explored. Topics discussed include; (1) resistance to planning activities and plans, (2) motivation for improved performance against plans, (3) cognitive limitations in implementing plans, and (4) blocks to innovate planning. Strategies for facilitating the implementation of planning models in each of these areas are reviewed.     

Behavioral aspects of corporate planning

Most models of corporate planning neglect to include behavioral variables. This is unfortunate, as human behavior is typically the most dynamic component of any planning system. Should behavioral variables be overlooked, due to their difficult measurability, or for other reasons, the planning system will inevitably prove deficient in terms of predictability and control. Accounting for human resources and other behavioral measurements should be routinely included in any corporate planning model. A component of such a system would include the output from a stochastic process model of expected future values of employee services. The theoretical development of such a model is briefly discussed in this paper.     

Dynamic aspects of line balancing

The article explores the dynamic nature of line balancing. Models are developed to help management with the problem of manning a line to produce a specified output. The models quantify the fluctuations in both excess inventories and the number of operators required.     

Some aspects of price strategy

A firm's success, within a rapidly growing and dynamic market, depends upon its ability to respond to market demand and to react to competitive forces. A key factor determining success is the pricing policy employed by the firm. Product pricing, however, is not simple; supply and demand, as well as the interaction and reaction of competitors, must be taken into consideration. By simulating a competitive market environment, however, a firm should be able to evaluate different pricing strategies prior to employing a strategy in practice. The goal of this research was to propose a simulation model to serve this purpose. Particularly, the objective was to demonstrate that if an industry can be characterized as one in which cost as well as price decline with cumulative volume, a pricing policy leading to market dominance exists. A simulation model is desirable for evaluating the proper pricing strategy for achieving such a market position.     

Closest targets and strong monotonicity on the strongly efficient frontier in DEA

The determination of closest efficient targets has attracted increasing interest of researchers in recent Data Envelopment Analysis (DEA) literature. Several methods have been introduced in this respect. However, only a few attempts exist that analyze the implications of using closest targets on the technical inefficiency measurement. In particular, least distance measures based on Hölder norms satisfy neither weak nor strong monotonicity on the strongly efficient frontier. In this paper, we study Hölder distance functions and show why strong monotonicity fails. Along this line, we provide a solution for output-oriented models that allows assuring strong monotonicity on the strongly efficient frontier. Our approach may also be extended to the most general case, i.e. non-oriented models, under some conditions of regularity.     

Some statistical aspects of manpower planning in the civil service

A special feature of modern manpower planning methods is the use of computer-based statistical models, and the Civil Service Department is taking the lead in their development and use for manpower planning in the non-industrial Civil Service. Account is being taken of related data requirements in the development of a new Personnel Record Information System which will replace a range of existing records.Development work in hand covers both the “demand” and “supply” aspects of manpower planning and a bank of generalized “supply” models is in operation. Stationary population, renewal and Markovian principles are involved, and the particular statistical problems of modelling small manpower groups are being met in the development of a “small group” simulation model.     

Behavioural aspects of marketing information systems

A survey of 84 users of marketing information systems in 33 companies was conducted to determine the relationship between usage of their systems and (i) attitude factors, (ii) perceived organizational factors, (iii) personality dimensions. Principal components analysis was used to derive underlying attitude and organizational factors as measured by responses to a series of statements derived from exploratory research. Personality was measured by means of the Eysenck Personality Inventory. Usage of the system was measured by seven usage variables constructed to capture the various dimensions of usage identified at the exploratory stage of the research. A series of multiple regressions were used to relate the criterion variables (usage dimensions) to each of the predictor variables (attitude factors, perceived organizational factors, and personality). A number of attitude factors, and perceived organizational factors was found to be significantly related to usage. In the main, personality was not related to usage. The results support earlier research in the USA which indicate association between attitudes and usage, and point to the importance of researching organizational aspects which may affect usage. A number of specific features of marketing information systems design is supported by the results of this study. The paper, therefore, provides an analysis of a wider number of factors which may be related to use than earlier studies, provides statistical support for a number of design issues, relates American findings to British experience and is based upon a larger and more comprehensive sample than previous research.     

Some methodological aspects of innovation research

From the policy point of view it is essential to understand the links between firm and management characteristics and the outcome of the firm's innovative endeavours, i.e. success or failure. This is achieved via firm behaviour variables, and the causal links between variables at all three levels (characteristics, behaviour, outcome) are demonstrated using interelated sub-systems of variables derived from empirical data obtained from the SAPPHO results.     

Self-concept based aspects of the charismatic leader: More than meets the eye

This research examines the relationships among leader self-concept based dispositional attributes (i.e., self-consciousness, self-monitoring, and purpose-in-life) with ratings of charismatic leadership. Questionnaires were used to collect data from different sources: 64 managers rated themselves on self-concept based dispositional attributes, while 194 subordinates assessed their manager's leadership style. Results indicated that leader private self-consciousness, self-monitoring, and purpose-in-life were positively related to charismatic leadership. Leader purpose-in-life was negatively related to both private and public self-consciousness. Private self-consciousness was positively related to self-monitoring. Results are discussed in terms of their theoretical and practical implications.     

合作的逻辑: 基于强欺骗策略的演化分析

如何解释非亲缘关系之间的合作现象? 合作演化(evolution of cooperation) 研究在多人囚徒困境博弈模型基础上提出一系列理论上的解释． 作者利用”基于主体建模”方法建立了基于惩罚策略的合作演化模型． 模型中有两种惩罚策略． 一种是强合作策略,即合作且惩罚不合作者; 另一种是强欺骗策略,即不合作且惩罚不合作者． 模拟结果说明,虽然强合作策略在个体层面有利合作,却可能在宏观上破坏合作秩序; 强欺骗策略在微观上不利于合作,但在整体上, 即使是在较大规模的社会中可能有助于社会合作的形成,因为该策略主体在形成不稳定联盟或多个联盟时会导致出现合作与非合作并存的混合策略均衡,也即虽然不能在最优水平,却在次优水平上实现稳定的社会合作．