Search

In this paper, we take a mechanism design approach to optimal assignment problems with asymmetrically informed buyers. In addition, the surplus generated by an assignment of a buyer to a seller may be adversely affected by externalities generated by other assignments. The problem is complicated by several factors. Buyers know their own valuations and externality costs but do not know this same information for other buyers. Buyers also receive private signals correlated with the state and, consequently, the implementation problem exhibits interdependent valuations. This precludes a naive application of the VCG mechanism and to overcome this interdependency problem, we construct a two-stage mechanism. In the first stage, we exploit correlation in the firms signals about the state to induce truthful reporting of observed signals. Given that buyers are honest in stage 1, we then use a VCG-like mechanism in stage 2 that induces honest reporting of valuation and externality functions. [ABSTRACT FROM AUTHOR]

Jacobi's results on the computation of the order and of the normal forms of a differential system are translated in the formalism of differential algebra. In the quasi-regular case, we give complete proofs according to Jacobi's arguments. The main result is Jacobi's bound, still conjectural in the general case: the order of a differential system P 1 , ... , P n is not greater than the maximum O of the sums ∑ i = 1 n a i , σ (i) , for all permutations σ of the indices, where a i , j : = ord x j P i , viz. the tropical determinant of the matrix (a i , j) . The order is precisely equal to O iff Jacobi's truncated determinant does not vanish. Jacobi also gave a polynomial time algorithm to compute O , similar to Kuhn's "Hungarian method" and some variants of shortest path algorithms, related to the computation of integers ℓ i such that a normal form may be obtained, in the generic case, by differentiating ℓ i times equation P i . Fundamental results about changes of orderings and the various normal forms a system may have, including differential resolvents, are also provided. [ABSTRACT FROM AUTHOR]

A central stability notion for allocation problems when there are private endowments is core: no coalition should be able to block the allocation. But, for an exchange economy of discrete resources, core can be empty. An alternative stability axiom is the bargaining set à la Aumann and Maschler (Advances in game theory, Annals of mathematics studies, Princeton University Press, Princeton, pp 443–476, 1964): a blocking by a coalition is justified only if there is no counter-objection to it and an allocation is in the bargaining set if there does not exist a justified blocking. Allowing for weak preferences, we prove that any allocation obtained by the well-known Top Trading Cycles class is in the bargaining set, but not all allocations in the bargaining set can be obtained by this class. [ABSTRACT FROM AUTHOR]

In this paper, we study the general restricted inverse assignment problems, in which we can only change the costs of some specific edges of an assignment problem as less as possible, so that a given assignment becomes the optimal one. Under l 1 norm, we formulate this problem as a linear programming. Then we mainly consider two cases. For the case when the specific edges are only belong to the given assignment, we show that this problem can be reduced to some variations of the minimum cost flow problems. For the case when every specific edge does not belong to the given assignment, we show that this problem can be solved by a minimum cost circulation problem. In both cases, we present some combinatorial algorithms which are strongly polynomial. We also study this problem under the l ∞ norm. We propose a binary search algorithm and prove that the optimal solution can be obtained in polynomial time. [ABSTRACT FROM AUTHOR]

First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the ϵ -scaling auction algorithm, the Hungarian algorithm and the FlowAssign algorithm. The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity. [ABSTRACT FROM AUTHOR]

A well known identifiability issue in factor analytic models is the invariance with respect to orthogonal transformations. This problem burdens the inference under a Bayesian setup, where Markov chain Monte Carlo (MCMC) methods are used to generate samples from the posterior distribution. We introduce a post-processing scheme in order to deal with rotation, sign and permutation invariance of the MCMC sample. The exact version of the contributed algorithm requires to solve 2 q assignment problems per (retained) MCMC iteration, where q denotes the number of factors of the fitted model. For large numbers of factors two approximate schemes based on simulated annealing are also discussed. We demonstrate that the proposed method leads to interpretable posterior distributions using synthetic and publicly available data from typical factor analytic models as well as mixtures of factor analyzers. An R package is available online at CRAN web-page. [ABSTRACT FROM AUTHOR]

Two-level priority based assignment problem (2PBAP) is an important optimization problem due to the timely delivery requirement in project management. Only four methods with deficiency are available in the literature to solve 2PBAP. In this paper, 2PBAP is reduced to a series of finding the feasible flow in a network with lower and upper arc capacities, and consequently two iterative algorithms are developed to solve 2PBAP. It is proved that both iterative algorithms find the optimal solution to 2PBAP in a strongly polynomial time. Owing to having fully utilized the network flow structural characteristic inherent to 2PBAP, both iterative algorithms have the advantages such as easy implementation on computer, no memory overflow in implementation on computer for large scale instances, high computational efficiency, and easy extension to the priority based assignment problem with priority level more than two, and successfully overcome the deficiency of existing approaches. Computational experiments validate that in terms of computational time, one of our proposed iterative algorithms has higher efficiency than the other, and rivals the existing best approach. [ABSTRACT FROM AUTHOR]

Decomposition NLP/LP/NLP methods are considered for the automated process design of the economically optimal distributed heat exchange networks between process streams using the assignment problem. The principle of fixation of intermediate variables and issues of the design of the superstructures of a heat exchange network and their decomposition are discussed. Methods to reduce the computational effort to solve the problems of the optimal heat integration are analyzed. The proposed synthesis methods are studied using the example of a mash distillation plant, and the problem of synthesizing the optimal multistage heat exchange network and the split-stream heat exchange network is solved. [ABSTRACT FROM AUTHOR]

Under consideration is the following strongly NP-hard problem: Given a balanced complete bipartite graph with weights on the edges and a partition of one of its parts into nonempty and pairwise disjoint subsets, find a perfect matching of this graph such that the maximum total weight of edges of the matching incident to vertices of one subset of the partition is minimal. We propose some characterization of solutions for a special case of this problem in which, firstly, the weights of graph edges take values in , where is an integer greater than the number of edges of the unit weight; and, secondly, there is a perfect matching of the graph that consists of the edges only with weights and . Moreover, we identify the cases of problems that are polynomially solvable and strongly NP-hard. Finally, we show that if the number of subsets forming the partition of the special part of the graph is fixed then the problem is equivalent to finding a perfect matching of a given weight in an edge-weighted bipartite graph. [ABSTRACT FROM AUTHOR]

In this paper, a bi-objective priority based assignment problem (BPBAP) related to an industrial project, is considered in which, depending upon the work breakdown structure, the n tasks involved in the project are divided into two categories. One of the categories consists of m primary tasks and the other one consists of (n - m) secondary tasks (for m < n ). The project is such that the secondary tasks can be executed only after the primary tasks are finished, however, the tasks within each category may be executed simultaneously. This problem is a special case of categorized assignment scheduling problem, discussed extensively in literature. The BPBAP is studied with the objective of minimizing simultaneously, the two criteria namely, total execution time and total assignment cost of the project which are equal to the sum of execution times and assignment costs respectively, of primary and secondary tasks. Generally, it is not possible to optimize both the objectives simultaneously, therefore, there is a need to do time-cost trade-off analysis of the problem. Since, the present problem is based on two-stage execution of the project (one stage for each category of tasks), therefore, a criteria based iterative algorithm considering all the possible combinations of the parameters of both the categories, is developed that finds all the non-dominated points of BPBAP in a polynomial time. Numerical illustrations are provided in the support of theory. [ABSTRACT FROM AUTHOR]

We consider the Random Euclidean Assignment Problem in dimension d = 1 , with linear cost function. In this version of the problem, in general, there is a large degeneracy of the ground state, i.e. there are many different optimal matchings (say, ∼ exp (S N) at size N). We characterize all possible optimal matchings of a given instance of the problem, and we give a simple product formula for their number. Then, we study the probability distribution of S N (the zero-temperature entropy of the model), in the uniform random ensemble. We find that, for large N, S N ∼ 1 2 N log N + N s + O log N , where s is a random variable whose distribution p(s) does not depend on N. We give expressions for the moments of p(s), both from a formulation as a Brownian process, and via singularity analysis of the generating functions associated to S N . The latter approach provides a combinatorial framework that allows to compute an asymptotic expansion to arbitrary order in 1/N for the mean and the variance of S N . [ABSTRACT FROM AUTHOR]

Uncertain random expected value simulation is one of the most important techniques to solve uncertain random optimization problems where random variables coexist with uncertain variables. A general simulation algorithm is designed to estimate the uncertain random expected value. Furthermore, an uncertain random quadratic bottleneck assignment problem is proposed and an uncertain random expected value model is presented. An algorithm is designed to find a lower bound of the uncertain random quadratic bottleneck assignment problem. [ABSTRACT FROM AUTHOR]

A new approach to the synthesis of a multistage heat exchange network is proposed based on the principle of fixation of variables. This principle enables one to reduce a discrete-continuous programming problem to a sequence of linear and nonlinear programming problems. For their formalization, a new variant of the superstructure of a heat exchange network is put forward which includes all the possible flow patterns of material and heat streams. A computational experiment has proven that this problem is multiextremal. The vertical decomposition of the superstructure decreases the number of local minima of an economic criterion and reduces the computational difficulty of the synthesis problem, which is useful for modeling large-scale engineering systems. The performance of the proposed algorithm is demonstrated by a number of model examples in comparison with that of the efficient SYNHEAT software. [ABSTRACT FROM AUTHOR]

In fields like transport or materials sourcing, it is common industrial practice nowadays to contract several partners for the fulfilment of similar sets of tasks. A typical approach is to include quotes to the contracts that specify which portion of the total volume should be given to each partner. In this study, which is inspired by a real-world problem, we examine the question of operationally distributing jobs to a set of partners in order to meet the contracted quotes in different dimensions as closely as possible. We propose the term fair task allocation problem and analyze its complexity. While the problem is NP-hard in the strong sense for the general case, we show that it is solvable in pseudopolynomial time for a given number of partners and dimensions. Besides an exact solution approach based on dynamic programming, we present an efficient Tabu Search procedure. The Tabu Search is applied to real world as well as to self-generated instances. To verify its quality, the results are compared to the solutions of a commercial MIP-solver. [ABSTRACT FROM AUTHOR]

Uncertain random simulation plays an important role in solving uncertain random optimization problems that include random variables and uncertain variables. In this paper, an uncertain random simulation is proposed and developed to obtain the chance distribution, α -pessimistic value and α -optimistic value. Further, an α -optimal model for the uncertain random bottleneck assignment problem under the Hurwicz criterion is presented. Finally, a numerical example is given to illustrate how to use the proposed simulation algorithm to solve an uncertain random bottleneck assignment problem. [ABSTRACT FROM AUTHOR]

We study the House Allocation problem (also known as the Assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomised mechanisms. We give a natural and explicit extension of the classical Random Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation problem where preference lists can include ties. We thus obtain a universally truthful randomised mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of e e - 1 . The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of 18 13 on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. By using a characterisation result of Bade, we show that any randomised mechanism that is a symmetrisation of a truthful, non-bossy and Pareto optimal mechanism has an improved lower bound of e e - 1 . Since our new mechanism is a symmetrisation of RSDM for strict preferences, it follows that this lower bound is tight. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomised strategy of the administrator who interviews the applicants. [ABSTRACT FROM AUTHOR]

Theory and applications of fractional programming have been significantly developed in the few last decades and assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization. Generally, in real world problems, the possible values of coefficients of a linear fractional programming problem are often only imprecisely or ambiguously known to the decision maker, therefore, it would be certainly more appropriate to interpret the coefficients as fuzzy numerical data. In this article, a fuzzy bi-objective fractional assignment problem has been formulated. Here the parameters are represented by triangular fuzzy numbers and the fuzzy problem is transformed into standard crisp problem through α -cut and then the compromise solution is derived by fuzzy programming. [ABSTRACT FROM AUTHOR]

In the classical secretary problem, multiple secretaries arrive one at a time to compete for a single position, and the goal is to choose the best secretary to the job while knowing the candidate's quality only with respect to the preceding candidates. In this paper we define and study a new variant of the secretary problem, in which there are multiple jobs. The applicants are ranked relatively upon arrival as usual, and, in addition, we assume that the jobs are also ranked. The main conceptual novelty in our model is that we evaluate a matching using the notion of blocking pairs from Gale and Shapley's stable matching theory. Specifically, our goal is to maximize the number of matched jobs (or applicants) that do not take part in a blocking pair. We study the cases where applicants arrive randomly or in adversarial order, and provide upper and lower bounds on the quality of the possible assignment assuming all jobs and applicants are totally ordered. Among other results, we show that when arrival is uniformly random, a constant fraction of the jobs can be satisfied in expectation, or a constant fraction of the applicants, but not a constant fraction of the matched pairs. [ABSTRACT FROM AUTHOR]

This paper sustains a sound mathematical and computing background. In this paper, the software-based approach for solving intuitionistic fuzzy solid assignment problem (IFSAP) is presented. The IFSAP is formulated and it is solved by using Lingo 17.0 software tool. Theorems related to IFSAP is proved. The IFSAP and its crisp solid assignment problem both are solved at a time and their optimal solution is obtained. In addition, the optimal objective values of both the IFSAP and its crisp solid assignment problem (SAP) are estimated with the help of substituting the optimal solution(s) to their respective decision variables in the objective functions. Some new and important results are proposed. To illustrate the efficiency of the proposed method the numerical example is presented. The reliability of the proposed results are verified by using the numerical example. Strengths and weakness of the paper is mentioned. The novelty of the analysis is given into a coherent, concise, and meaningful manner of analysis. Social issue (real-life problem) is converted into a mathematical model and it is solved by the proposed method. At the end, the advantages of the proposed algorithm is explained. [ABSTRACT FROM AUTHOR]

We consider a one-to-one assignment problem consisting of matching n objects with n agents. Any matching leads to a utility vector whose n components measure the satisfaction of the various agents. We want to find an assignment maximizing a global utility defined as an ordered weighted average (OWA) of the n individual utilities. OWA weights are assumed to be non-increasing with ranks of satisfaction so as to include an idea of fairness in the definition of social utility. We first prove that the problem is NP-hard; then we propose a polynomial algorithm under some restrictions on the set of admissible weight vectors, proving that the problem belongs to XP. [ABSTRACT FROM AUTHOR]

A sonobuoy is an underwater acoustic sensor primarily deployed by airdrop. An acoustic sensor plays a significant role in conducting anti-submarine warfare for detecting underwater sounds. As a future underwater acoustic sensor, sonobuoy is expected to have an ability of self-movement, i.e., autonomous sonobuoy. In this study, we consider an optimal linear array deployment of autonomous sonobuoys when detecting an unknown underwater sound, assuming that the initial locations of sonobuoys are random in a specified operational area. Deploying sonobuoys from the initial locations onto a specific line requires to first determine the line and positions on that line. Under the interval equivalence between two adjacent sonobuoys, we propose two lines, one that is perpendicular from the underwater sound source location and the other based on the linear regression analysis using the initial locations of sonobuoys. With these two lines onto which sonobuoys will be deployed, we provide two optimization models, total distance minimization and maximum distance minimization, which turn out to be assignment and bottleneck assignment problems, respectively, with nonlinear cost coefficients in the objectives. Due to non-convexity of the objectives, we solve these problems for a fixed interval repetitively as a linear program and integer program, respectively. Computational results show that regression-based line provides higher solution qualities for both problems. Finally, we suggest an approximate interval in a heuristic manner, which guarantees a highly near-optimality as the number of sonobuoys increases. Our results may support a decision-making and provide practitioners with insight on more variety of effective use of autonomous sonobuoys. [ABSTRACT FROM AUTHOR]

Abstract: A new algorithmic approach to the synthesis of economically optimum multistage heat exchange network in the design and reconstruction of chemical-technological units has been considered. The problem was proposed to be solved based on the assignment problem and decomposition principle of fixation of variables. The efficiency of the approach was shown on the example of solving a number of typical problems on heat integration. [ABSTRACT FROM AUTHOR]

We consider combinatorial algorithms for the minimum-cost flow problem on networks with unit capacities, and special cases of the problem. Historically, researchers have developed special-purpose algorithms that exploit unit capacities. In contrast, for the maximum flow problem, the classical blocking flow and push-relabel algorithms for the general case also have the best bounds known for the special case of unit capacities. In this paper we show that the classical blocking flow push-relabel cost-scaling algorithms of Goldberg and Tarjan (Math. Oper. Res. 15, 430-466, 1990) for general minimum-cost flow problems achieve the best known bounds for unit-capacity problems as well. We also develop a cycle-canceling algorithm that extends Goldberg's shortest path algorithm (Goldberg SIAM J. Comput. 24, 494-504, 1995) to minimum-cost, unit-capacity flow problems. Finally, we combine our ideas to obtain an algorithm that solves the minimum-cost bipartite matching problem in $O(r^{1/2} m \log C)$ time, where m is the number of edges, C is the largest arc cost (assumed to be greater than 1), and r is the number of vertices on the small side of the vertex bipartition. This result generalizes (and simplifies) a result of Duan et al. (2011) and solves an open problem of Ramshaw and Tarjan (2012). [ABSTRACT FROM AUTHOR]

In this paper, we present the existing literature on the human resource allocation problem. We study the main resolution approaches: exact, heuristic and metaheuristics methods proposed to solve the problem. We also examine the different studies from state-of the-art and classify them according to their real life applications in several areas such as production planning applications, maintenance management, hospital systems, project management, etc. Finally, we discuss and analyze the different contributions examined in this field. [ABSTRACT FROM AUTHOR]

We present a consensus method which, given the two correspondences between sets of elements generated by separate entities, enounces a final correspondence consensus considering the existence of outliers . Our method is based on an optimisation technique that minimises the cost of the correspondence while forcing (to the most) to be the mean correspondence of the two original correspondences. The method decides the mapping of the elements that the original correspondences disagree and returns the same element mapping when both correspondences agree. We first show the validity of the method through an experiment in ideal conditions based on palmprint identification, and subsequently present two practical experiments based on image retrieval. [ABSTRACT FROM AUTHOR]

With the popularity of mobile computing and social media, various kinds of online event-based social network (EBSN) platforms, such as Meetup, Plancast and Whova, are gaining in prominence. A fundamental task of managing EBSN platforms is to recommend suitable social events to potential users according to the following three factors: spatial locations of events and users, attribute similarities between events and users, and friend relationships among users. However, none of the existing approaches considers all the aforementioned influential factors when they recommend users to proper events. Furthermore, the existing recommendation strategies neglect the bottleneck cases of the global recommendation. Thus, it is impossible for the existing recommendation solutions to be fair in real-world scenarios. In this paper, we first formally define the problem of bottleneck-aware social event arrangement (BSEA), which is proven to be NP-hard. To solve the BSEA problem approximately, we devise two greedy heuristic algorithms, Greedy and Random+Greedy, and a local-search-based optimization technique. In particular, the Greedy algorithm is more effective but less efficient than the Random+Greedy algorithm in most cases. Moreover, a variant of the BSEA problem, called the Extended BSEA problem, is studied, and the above solutions can be extended to address this variant easily. Finally, we conduct extensive experiments on real and synthetic datasets which verify the efficiency and effectiveness of our proposed algorithms. [ABSTRACT FROM AUTHOR]

The well-known problem of weighted matching in an arbitrary graph H with n vertices is reduced to a matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H with the minimum sum of weights of edges defined by matrix[c] is found in timeO ( n ) after ordering, in non-descending order, the values above the main diagonal. [ABSTRACT FROM AUTHOR]

Underlay device-to-device (D2D) communication in cellular networks has been considered as a promising technique that can improve the spectral efficiency of cellular systems and meet the growing demand for wireless local services. In underlay D2D, it is of primary importance to manage the mutual interference between cellular links and D2D links through effective resource allocation. While most of previous works on D2D resource allocation are developed based on the knowledge of the channel state information (CSI) on the interference channels as well as the desired channels, it is hard to obtain full CSI in practice. Accordingly, we consider D2D resource allocation schemes based on distance between nodes. In particular, we formulate two optimization problems for D2D resource allocation using the outage probability computed based on the distance information as cost functions. One is a linear sum assignment problem (LSAP) and the other is a linear bottleneck assignment problem (LBAP). By applying the graph theory, we provide efficient algorithms for solving the optimization problems. Numerical results are provided to show the effectiveness of the proposed optimization as compared to previously proposed distance-based resource allocation algorithms. [ABSTRACT FROM AUTHOR]

Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact. [ABSTRACT FROM AUTHOR]

The paper considers the minimization of the sum of weights of edges forming a subset U′ ⊂ U of the set of disjoint simple cycles at vertices υ ϵ V in graph H = (V,U) and covering V. The problem under study (2-f problem) is polynomially solvable in algorithms that are characterized by technical difficulties that hinder the acceleration of computing. The 2-f problem is solved by reducing it to a simpler bipartite case. The result is represented by a perfect matching of bipartite graph corresponding to the solution of the assignment problem, where each circuit of cyclic expansion contains at least three arcs. [ABSTRACT FROM AUTHOR]

We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP-hard in general, we also describe some restricted cases that can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

The approach to the problem of designing optimal heat-exchange networks for the reconstruction and synthesis of distillation columns is discussed. It has been proposed to reduce the original discrete-continuous nonlinear programming problem to the modified linear programming assignment problem that takes into account a number of features of separation systems. [ABSTRACT FROM AUTHOR]

We consider systems of small, cheap, simple sensors that are organized in a distributed network and used for estimating and tracking the locations of targets. The objective is to assign sensors to targets such that the overall expected error of the sensors' estimates of the target locations is minimized. The so-called focus of attention problem (FOA) deals with the special case where every target is tracked by one pair of range sensors. The resulting computational problem is a special case of the axial three-index assignment problem, a well-known fundamental problem in combinatorial optimization. We provide a complete complexity and approximability analysis of the FOA problem: we establish strong NP-hardness and the unlikeliness of an FPTAS, we identify polynomially solvable special cases, and we construct a sophisticated polynomial time approximation scheme for it. [ABSTRACT FROM AUTHOR]

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer. [ABSTRACT FROM AUTHOR]

Analysing the characters of the elements of the efficiency matrix of the assignment problem, we find some properties of the optimal solution. Different from the traditional algorithm, Hungarian method, we give several principles to recognize some optimal points rapidly, thus we can reduce the dimension of the assignment problem. [ABSTRACT FROM AUTHOR]

We propose a local search method with a new exponential neighborhood for the servers load balancing problem. Under study are some variants of the local search algorithms with randomized versions of this neighborhood. The computational results are provided that confirm high efficiency of the approach. [ABSTRACT FROM AUTHOR]

This paper presents a multi-objective linear integer program that assigns student volunteers to present lectures at participating classes in local schools. A student's class assignment is based upon his or her availability to teach at that time as well as several additional factors including student preferences regarding commuting and partners as well as the institution's goal of creating diverse student groups. This case study shows that the proposed mathematical program dramatically improves the assignments of students to classes and provides increased flexibility for modeling other goals and factors in future years. In addition, this multi-phase model can be applied in other contexts, such as crew scheduling or the scheduling of parallel sessions of large conferences. [ABSTRACT FROM AUTHOR]

An implementation of evolutionary heuristic algorithm, which is a specific modified variant of cultural algorithm, with simplified computational procedure is presented here for solving assignment problems. A cultural algorithm consists a population component almost identical to that of the genetic algorithm and, in addition, a knowledge component called the belief space. The major constraint of assignment problems that a single job can be assigned to only one resource and the resource or job that involves the largest and as well as the least cost are availed as the knowledge components to be used to build belief space. [ABSTRACT FROM AUTHOR]

The multichannel recordings of signals of many cells cultivated on a multielectrode array (MEA) impose some challenging problems. A meanwhile classic problem is the separation of the recordings of a single electrode into classes of recordings where each class is caused by a single cell. This is the well-known spike sorting. A 'dual' problem is the determination of the set of electrodes that record signals of a single cell. This set is called the neighborhood of the cell and has often more than one element if the MEA has a large number of electrodes with high density. A method for the reconstruction of the neighborhoods from the multichannel recordings is presented. Special effort is directed to a precise peak detection. For the evaluation of the algorithm, artificial data, obtained from an appropriate model of MEA recordings, are used. Because the artificial data provide a ground truth, an evaluation of the accuracy of the algorithm is possible. The algorithm works well for realistic parameters. [ABSTRACT FROM AUTHOR]

Personnel scheduling problems can be decomposed into two stages. In the first stage for each employee the working days have to be fixed. In the second stage for each day of the planning period an intraday scheduling problem has to be solved. It consists of the assignment of shifts to the employees who have to work on the day and for each working period of an employee a task assignment such that the demand of all tasks for personnel is covered. In Robinson et al. (Burke and Trick (Eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, 18th August-20th August 2004, Pittsburgh, PA, USA, pp. 561-566, ), the intraday problem has been formulated as a maximum flow problem. The assumptions are that, employees are qualified for all tasks, their shifts are given, and they are allowed to change tasks during the day. In this work, we extend the network flow model to cover the case where not all employees are qualified to perform all tasks. The model is further extended to be able to calculate shifts of employees for the given day, assuming that an earliest starting time, a latest finishing time, and a minimal working time are given. Labour cost can be also taken into account by solving a minimum cost network flow problem. [ABSTRACT FROM AUTHOR]

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses' preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. [ABSTRACT FROM AUTHOR]

The linear bottleneck assignment problem (LBAP), which is a variation of the classical assignment problem (CAP), seeks to minimize the longest completion time rather than the sum of the completion times when a number of jobs are to be assigned to the same number of workers. Several procedures have been proposed in the current literature to convert the LBAP into an equivalent CAP and then apply the Hungarian method to solve it efficiently. However, their applicability is limited because some of the elements in the transformed assignment matrix for the CAP can be too large to be handled by most computer programs. In this paper, we suggest a turnpike approach to alleviate the problem so that the conversion methodology will become more useful in practice. A numerical example is provided to demonstrate the superiority of the new algorithm to the existing ones. [ABSTRACT FROM AUTHOR]

This paper is to analyze unrelated parallel-machine scheduling resource allocation problems with position-dependent deteriorating jobs. Two general resource consumption functions, the linear and convex resource, are investigated. The objectives are to minimize the cost function that includes the weights of total load, total completion time, total absolute deviation of completion time, and total resource cost. Moreover, we try to minimize the cost function that includes the weights of total load, total waiting time, total absolute deviation of waiting time, and total resource cost. Although each job processing time can be compressed through incurring an additional cost, we show that the problems are polynomial time solvable when the number of machines is fixed. [ABSTRACT FROM AUTHOR]