Evolutionary insights on the willingness to communicate

While in previous models of pre-play communication players are forced to communicate, we investigate what happens if players can choose not to participate in this cheap talk. Outcomes are predicted by analyzing evolutionary stability in a population of a priori identical players. If the game following the communication rewards players who choose the same action then an efficient outcome is only guaranteed when participation in the pre-play communication is voluntary. If however players aim to coordinate on choosing different actions in the underlying game and there are sufficiently many messages then the highest payoff is selected when players are forced to talk to each other before playing the game. Received: September 2000/Revised: March 2003     

An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007

Track 2 of the international timetabling competition 2007 was a post enrolment course timetabling problem. A set of events has to be assigned to a timeslot and to a room such that all students are able to attend their requested events while not violating the hard constraints. There are also soft constraints that make the timetable “nicer”.     

Approximation algorithms for the test cover problem

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics. Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Partially supported by a Merck Computational Biology and Chemistry Program Graduate Fellowship from the Merck Company Foundation.Also Iceland Genomics CorporationPartially supported by subcontract No. 16082-RFP-00-2C in the area of ``Combinatorial Optimization in Biology (XAXE),' Los Alamos National Laboratories, and NSF grant CCR-0105548.Mathematics Subject Classification: 90B27     

Stable multi-skill workforce assignments

This paper analyzes stability in multi-skill workforce assignments of technicians and jobs. In our stability analysis, we extend the notion of blocking pairs as stated in the Marriage model of Gale-Shapley to the multi-skill workforce assignment. It is shown that finding stable assignments is NP-hard. A special case turns out to be solvable in polynomial time. For the general case, we give a characterization of the set of stable assignments by means of linear inequalities involving binary variables. We propose an integer programming (IP) model to construct optimal stable assignments with several objectives. In the computational results, we observe that it is easier to attain stability in instances with easy jobs and we consider a range of instances to show how fast the solution time increases. Open questions and further directions are discussed in the conclusion section.     

On the nearest neighbor rule for the traveling salesman problem

Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145-180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor above the length of the optimal tour.We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.     

Complexity and approximation of an area packing problem

Motivated by an application in mobile telecommunication systems, we investigate a packing problem in which items are specified in terms of area constraints. We establish strong _boxclose{{\mathcal {NP}}}-hardness of this problem, provide a linear time 3-approximation algorithm, and discuss the combinatorics of a special case.     

Optimal packet-to-slot assignment in mobile telecommunications

The problem of assigning information packets of different services to time slots of a radio frame is addressed. Packet sizes are divisible, and a maximum time slot to which a packet can be assigned is given. We present a polynomial-time scheduling algorithm maximizing the number of scheduled packets.     

A BRANCH-AND-PRICE ALGORITHM FOR SOLVING THE CUTTING STRIPS PROBLEM

After giving a suitable model for the cutting strips problem, we present a branch-and-price algorithm for it by combining the column generation technique and the branch-and-hound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computarional experience is reported.