Simple games cover voting systems in which a single alternative, such as a bill or anamendment, is pitted against the status quo. A simple game or a yes-no voting system is aset of rules that specifies exactly which collections of “yea” votes yield passage of theissue at hand. Each of these collections of “yea” voters forms a winning coalition. We areinterested in performing a complexity analysis on problems defined on such families ofgames. This analysis as usual depends on the game representation used as input. Weconsider four natural explicit representations: winning, losing, minimal winning, andmaximal losing. We first analyze the complexity of testing whether a game is simple andtesting whether a game is weighted. We show that, for the four types of representations,both problems can be solved in polynomial time. Finally, we provide results on thecomplexity of testing whether a simple game or a weighted game is of a special type. Weanalyze strongness, properness, weightedness, homogeneousness, decisiveness andmajorityness, which are desirable properties to be fulfilled for a simple game. Finally,we consider the possibility of representing a game in a more succinct and natural way andshow that the corresponding recognition problem is hard.

In this paper we deal with the preemptive asymmetric stacker crane problem in a heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation an integer linear programming model together with simple and efficient greedy and local search heuristics. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and evaluating the impact of the preemption hypothesis.

This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n 3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions i.e. chain parenthesizations. Afterwards, we establish a comparison between these two algorithms based on the parallel computing of the matrix chain product through intra and inter-subchains coarse grain parallelism. Finally, an experimental study illustrates the theoretical parallel performances of the designed algorithms.

In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum solutions for all testedinstances. The semidefinite relaxation gives a lower bound $\frac{C}{W}$ and each heuristic produces a cut S with a ratio $\frac{c_S}{w_S}$, where either cS is at most a factor of C or wS is at least a factor of W. We solved the semidefinite relaxation using a semi-infinite cut generation with a commercial linear programming package adapted to the sparsest cut problem. We showed that the proposed strategy leads to a better performance compared to the use of a known semidefinite programming solver.

A hypergraph is Helly if every family of hyperedges of it, formed by pairwiseintersecting hyperedges, has a common vertex. We consider the concepts ofbipartite-conformal and (colored) bipartite-Helly hypergraphs. In the same way asconformal hypergraphs and Helly hypergraphs are dual concepts, bipartite-conformal andbipartite-Helly hypergraphs are also dual. They are useful for characterizing bicliquematrices and biclique graphs, that is, the incident biclique-vertex incidence matrix andthe intersection graphs of the maximal bicliques of a graph, respectively. These conceptsplay a similar role for the bicliques of a graph, as do clique matrices and clique graphs,for the cliques of the graph. We describe polynomial time algorithms for recognizingbipartite-conformal and bipartite-Helly hypergraphs as well as biclique matrices.

We consider a system consisting of two not necessarily identicalexponential servers having a common Poisson arrival process. Uponarrival, customers inspect the first queue and join it if it isshorter than some threshold n. Otherwise, they join the secondqueue. This model was dealt with, among others, by Altman et al. [Stochastic Models 20 (2004) 149–172].We first derive an explicitexpression for the Laplace-Stieltjes transform of the distributionunderlying the arrival (renewal) process to the second queue. Second,we observe that given that the second serveris busy, the two queue lengths are independent.Third, we develop two computational schemes for thestationary distribution of the two-dimensional Markov process underlying thismodel, one with a complexity of$O(n \log\delta^{-1})$, the other with a complexity of $O(\log n\log^2\delta^{-1})$, where δ is the tolerance criterion.

In this paper we introduce some improvements on an approach that we described elsewherefor solving a modification of the well-known extended rapid transit network designproblem. Firstly, we propose an integer programming model for selecting the stations to beconstructed and the links between them, in such a way that a connected rapid transitnetwork is obtained. Secondly, we consider a linear 0-1 programming model for determininga route of minimum length in the rapid transit network between certain pairs of locations,and present a greedy heuristic procedure which attempts to minimize an estimation of thetotal number of transfers that should be made by the users to arrive at theirdestinations. We also report several computational experiments that show that thisprocedure can significantly reduce the estimated total number of transfers required forthe solutions obtained using our previous approach.

Uncertainty in optimization is not a new ingredient. Diverse modelsconsidering uncertainty have been developed over the last 40 years.In our paper we essentially discuss a particular uncertainty modelassociated with combinatorial optimization problems, developed inthe 90's and broadly studied in the past years. This approach namedminmax regret (in particular our emphasis is on the robustdeviation criteria) is different from the classical approach for handlinguncertainty, stochastic approach, where uncertainty is modeledby assumed probability distributions over the space of all possiblescenarios and the objective is to find a solution with good probabilisticperformance. In the minmax regret (MMR) approach, the set of all possible scenariosis described deterministically, and the search is for a solution thatperforms reasonably well for all scenarios, i.e., that has the bestworst-case performance. In this paper we discuss the computational complexity of some classiccombinatorial optimization problems using MMR approach, analyze thedesign of several algorithms for these problems, suggest the studyof some specific research problems in this attractive area, and alsodiscuss some applications using this model.

In this paper, a single server finite buffer Markovian queuing system is analyzed with the additional restriction that customers may balk as well as renege. Reneging considered in literature is usually of position independent type where the reneging rate is constant irrespective of the position of the customer in the system. However there are many real world situations where this assumption does not hold. This paper is an attempt to model balking with position dependent reneging. Explicit closed form expressions of a number of performance measures are presented. A typical problem is discussed to demonstrate the usefulness of results derived in the paper.

This paper is motivated by operating self service transport systemsthat flourish nowadays. In cities where such systems have been setup with bikes, trucks travel to maintain a suitable number of bikesper station.It is natural to study a version of the C-delivery TSP defined byChalasani and Motwani in which, unlike their definition, C is partof the input: each vertex v of a graph G=(V,E) has a certainamount xv of a commodity and wishes to have an amount equal toyv (we assume that $\sum_{v\in V}x_v=\sum_{v\in V}y_v$ and allquantities are assumed to be integers); given a vehicle of capacityC, find a minimal route that balances all vertices, that is,that allows to have an amount yv of the commodity on each vertexv.This paper presents among other things complexity results, lowerbounds, approximation algorithms, and a polynomial algorithm whenG is a tree.

Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile, which is the final graph partitioning. This allows to evaluate the robustness of a cluster as the average percentage of partitions in the profile joining its element pairs ; this notion can be extended to partitions. Doing so, the initial and consensus partitions can be compared. A simulation protocol, based on random graphs structured in communities is designed to evaluate the efficiency of the Bootstrap Clustering approach.

This paper concerns a discrete time Geo[X]/G/1 retrial queue with general retrial time in which all the arriving customers require first essential service with probability $\alpha_{0}$ while only some of them demand one of other optional services: type − r (r = 1, 2, 3,...M) service with probability $\alpha_{r}$. The system state distribution, the orbit size and the system size distributions are obtained in terms of generating functions. The stochastic decomposition law holds for the proposed model. Performance measures of the system in steady state are obtained.  Finally, some numerical illustrations are presented to justify the influence of parameters on several performance characteristics.

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The second framework is probabilistic optimization, where the instance to optimize is not fully known at the time when a solution is to be proposed, but results from a determined Bernoulli process. Then, the goal is to compute a solution with optimal expected value.

Various topics related to reverse logistics have been discussed over the years. Most of them have assumed that facilities are kept open once they are established, and no returned products or recovery parts are stocked in intermediate recycling stations. However, firms may have the right to repeatedly open or close their facilities according to their economic benefits if they can acquire their facilities by lease. It also turns out that intermediate recycling stations like collection centers and disassembly centers usually stock returned products or parts in their facilities. By simultaneously relaxing these two assumptions, this study explores a logistics system with multiple items, each of which consists of some components among a variety of spare parts. The purpose is to maximize the total logistics costs by establishing a production schedule and reverse logistics framework over finite time periods for a logistics system. The mathematical model established in this study is a constrained linear integer programming problem. A genetic based algorithm is developed with the help of linear programming to find solutions to this problem. Limited computational experiments show that the proposed approach can produce better feasible solutions than the well-known CPLEX 10.0 software.

In this paper, we propose an exact solution method for the windy rural postman problem (WRPP). The motivation to study this problem comes from some real-life applications, such as garbage collecting in a predefined sector with hills, where the traversing or the servicing speed can change following the direction. We present a Dantzig-Wolfe decomposition and a branch-and-price algorithm to solve the WRPP. To the best of our knowledge, Dantzig-Wolfe decomposition has never been used to solve that problem. The numerical results show that optimal solutions are found in a very reasonable amount of time on instances with up to 100 nodes and 180 edges.

Data envelopment analysis (DEA) has been proven as an excellent data-oriented efficiency analysis method for comparing decision making units (DMUs) with multiple inputs and multiple outputs. In conventional DEA, it is assumed that the status of each measure is clearly known as either input or output. However, in some situations, a performance measure can play input role for some DMUs and output role for others. Cook and Zhu [Eur. J. Oper. Res. 180 (2007) 692–699] referred to these variables as flexible measures. The paper proposes an alternative model in which each flexible measure is treated as either input or output variable to maximize the technical efficiency of the DMU under evaluation. The main focus of this paper is on the impact that the flexible measures has on the definition of the PPS and the assessment of technical efficiency. An example in UK higher education intuitions shows applicability of the proposed approach.