Subhypergraph counts in extremal and random hypergraphs and the fractional <Emphasis Type="Italic">q</Emphasis>-independence

We study the extremal parameter N(n,m,H) which is the largest number of copies of a hypergraph H that can be formed of at most n vertices and m edges. Generalizing previous work of Alon (Isr. J. Math. 38:116–130, 1981), Friedgut and Kahn (Isr. J. Math. 105:251–256, 1998) and Janson, Oleszkiewicz and the third author (Isr. J. Math. 142:61–92, 2004), we obtain an asymptotic formula for N(n,m,H) which is strongly related to the solution α _q (H) of a linear programming problem, called here the fractional q-independence number of H. We observe that α _q (H) is a piecewise linear function of q and determine it explicitly for some ranges of q and some classes of H. As an application, we derive exponential bounds on the upper tail of the distribution of the number of copies of H in a random hypergraph.     

Popular matchings: structure and algorithms

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M′ such that more applicants prefer M′ to M than prefer M to M′. Abraham et al. (SIAM J. Comput. 37:1030–1045, 2007) described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre (Proceedings of MATCH-UP: Matching Under Preferences—Algorithms and Complexity, 2008).     

On Disjunctive Cuts for Combinatorial Optimization

In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-and-bound framework. Although researchers often prefer to use facet-inducing inequalities as cutting planes, good computational results have recently been obtained using disjunctive cuts, which are not guaranteed to be facet-inducing in general.A partial explanation for the success of the disjunctive cuts is given in this paper. It is shown that, for six important combinatorial optimization problems (the clique partitioning, max-cut, acyclic subdigraph, linear ordering, asymmetric travelling salesman and set covering problems), certain facet-inducing inequalities can be obtained by simple disjunctive techniques. New polynomial-time separation algorithms are obtained for these inequalities as a by-product.The disjunctive approach is then compared and contrasted with some other general-purpose frameworks for generating cutting planes and some conclusions are made with respect to the potential and limitations of the disjunctive approach.     

An improved approximation algorithm for uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the classical facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. The UFLWP problem has been effectively used to model the facility location problem with outliers. Three constant approximation algorithms have been obtained (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001; Jain et al. in J. ACM 50(6):795–824, 2003; Xu and Xu in Inf. Process. Lett. 94(3):119–123, 2005), and the best known performance ratio is 2. The only known hardness result is a 1.463-inapproximability result inherited from the uncapacitated facility location problem (Guha and Khuller in J. Algorithms 31(1):228–248, 1999). In this paper, We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm significantly reduces the gap between known performance ratio and the inapproximability result. Our algorithm first enhances the primal-dual method for the UFLWP problem (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001) so that outliers can be recognized more efficiently, and then applies a local search heuristic (Charikar and Guha in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pp. 378–388, 1999) to further reduce the cost for serving those non-rejected clients. Our algorithm is simple and can be easily implemented. The research of this work was supported in part by NSF through CAREER award CCF-0546509 and grant IIS-0713489. A preliminary version of this paper appeared in the Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON’05).     

Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks

All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2×2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435–446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435–446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini’s algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini’s algorithm to be applicable to d-nary (each switch is of size d×d) banyan multistage interconnection networks. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This research was partially supported by the National Science Council of the Republic of China under the grant NSC94-2115-M-009-006.     

Improving an exact approach for solving separable integer quadratic knapsack problems

We consider the specially structured (pure) integer Quadratic Multi-Knapsack Problem (QMKP) tackled in the paper “Exact solution methods to solve large scale integer quadratic knapsack problems” by D. Quadri, E. Soutif and P. Tolla (2009), recently appeared on this journal, where the problem is solved by transforming it into an equivalent 0–1 linearized Multi-Knapsack Problem (MKP). We show that, by taking advantage of the structure of the transformed (MKP), it is possible to derive an effective variable fixing procedure leading to an improved branch-and-bound approach. This procedure reduces dramatically the resulting linear problem size inducing an impressive improvement in the performances of the related branch and bound approach when compared to the results of the approach proposed by D. Quadri, E. Soutif and P. Tolla.     

On lazy bureaucrat scheduling with common deadlines

Lazy bureaucrat scheduling is a new class of scheduling problems introduced by Arkin et al. (Inf. Comput. 184:129–146, 2003). In this paper we focus on the case where all the jobs share a common deadline. Such a problem is denoted as CD-LBSP, which has been considered by Esfahbod et al. (Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We first show that the worst-case ratio of the algorithm SJF (Shortest Job First) is two under the objective function [min-time-spent], and thus answer an open question posed in (Esfahbod, et al. in Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We further present two approximation schemes A _k and B _k both having worst-case ratio of , for any given integer k>0, under the objective functions [min-makespan] and [min-time-spent], respectively. Finally, we prove that the problem CD-LBSP remains NP-hard under several objective functions, even if all jobs share the same release time. A preliminary version of the paper appeared in Proceedings of the 7th Latin American Symposium on Theoretical Informatics, pp 515–523, 2006. Research of G. Zhang supported in part by NSFC (60573020).     

On the existence of sports sentiment: the relation between football match results and stock index returns in Europe

We test for a relation between football match results and the specific national stock index returns during the period 1990–2006 by means of an event study approach. We employ two different econometric frameworks to cross-check our results and prevent them from being solely model driven: the constant mean model and a two-state Markov-switching market model. Both approaches find no significant results. Consequently, in a modified setup, we control for expectations about probable game results by applying a “surprise” variable, which is computed from betting odds and is integrated into a regression analysis. Again, there does not seem to be a connection between a specific national soccer team’s win or loss and stock index prices. In addition, through a few modifications in our empirical setup, we show how easy it would be to “produce” significant results. Our results are contrary to those of Ashton et al. (Appl Econ Lett 10:783–785, 2003) and Edmans et al. (J Finance 62(4):1967–1998, 2007) and support market efficiency.     

A new recombination lower bound and the minimum perfect phylogenetic forest problem

Understanding recombination is a central problem in population genetics. In this paper, we address an established computational problem in this area: compute lower bounds on the minimum number of historical recombinations for generating a set of sequences (Hudson and Kaplan in Genetics 111, 147–164, 1985; Myers and Griffiths in Genetics 163, 375–394, 2003; Gusfield et al. in Discrete Appl. Math. 155, 806–830, 2007; Bafna and Bansal in IEEE/ACM Trans. Comput. Biol. Bioinf. 1, 78–90, 2004 and in J. Comput. Biol. 13, 501–521, 2006; Song et al. in Bioinformatics 421, i413–i244, 2005). In particular, we propose a new recombination lower bound: the forest bound. We show that the forest bound can be formulated as the minimum perfect phylogenetic forest problem, a natural extension to the classic binary perfect phylogeny problem, which may be of interests on its own. We then show that the forest bound is provably higher than the optimal haplotype bound (Myers and Griffiths in Genetics 163, 375–394, 2003), a very good lower bound in practice (Song et al. in Bioinformatics 421, i413–i422, 2005). We prove that, like several other lower bounds (Bafna and Bansal in J. Comput. Biol. 13, 501–521, 2006), computing the forest bound is NP-hard. Finally, we describe an integer linear programming (ILP) formulation that computes the forest bound precisely for certain range of data. Simulation results show that the forest bound may be useful in computing lower bounds for low quality data. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 16–26. The work was performed while Y. Wu was with UC Davis and supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation. D. Gusfield supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation.     

New combinatorial structures with applications to efficient group testing with inhibitors

Group testing with inhibitors (GTI) is a variant of classical group testing where in addition to positive items and negative items, there is a third class of items called inhibitors. In this model the response to a test is YES if and only if the tested group of items contains at least one positive item and no inhibitor. This model of group testing has been introduced by Farach et al. (Proceedings of compression and complexity of sequences, pp 357–367, 1997) for applications in the field of molecular biology. In this paper we investigate the GTI problem both in the case when the exact number of positive items is given, and in the case when the number of positives is not given but we are provided with an upper bound on it. For the latter case, we present a lower bound on the number of tests required to determine the positive items in a completely nonadaptive fashion. Also under the same hypothesis, we derive an improved lower bound on the number of tests required by any algorithm (using any number of stages) for the GTI problem. As far as it concerns the case when the exact number of positives is known, we give an efficient trivial two-stage algorithm. Instrumental to our results are new combinatorial structures introduced in this paper. In particular we introduce generalized versions of the well known superimposed codes (Du, D.Z., Hwang, F.K. in Pooling designs and nonadaptive group testing, 2006; Dyachkov, A.G., Rykov, V.V. in Probl. Control Inf. Theory 12:7–13, 1983; Dyachkov, A.G., et al. in J. Comb. Theory Ser. A 99:195–218, 2002; Kautz, W.H., Singleton, R.R. in IEEE Trans. Inf. Theory 10:363–377, 1964) and selectors (Clementi, A.E.F, et al. in Proceedings of symposium on discrete algorithms, pp. 709–718, 2001; De Bonis, A., et al. in SIAM J Comput. 34(5):1253–1270, 2005; Indyk, P. in Proceedings of symposium on discrete algorithms, pp. 697–704, 2002) that we believe to be of independent interest.     

Hurricane Katrina, the Crisis of Leadership, and Chaos Management: Time for Trying the ‘Surprise Management Theory in Action’

Four years have gone by since the historic Hurricane Katrina hit and drowned the city of New Orleans and caused a massive crisis of, and a global case of grand failure in, governance, leadership, and public management. Advancing on an earlier work published in Public Administration Review (Farazmand 2007), in which a global case of grand failure was established with several lessons drawn for future crisis management, this article argues further for developing and applying a theory of ‘surprise management’ to manage future crises and chaotic situations. Crises are borne out of natural and human made disasters, catastrophes, revolutions, and rapidly changing emergencies. Surprise management is the best approach to managing or coping with crises and crisis driven emergencies.     

A linear programming duality approach to analyzing strictly nonblocking <Emphasis Type="Italic">d</Emphasis>-ary multilog networks under general crosstalk constraints

When a switching network topology is used for constructing optical cross-connects, as in the circuit switching case, no two routes are allowed to share a link. However, if two routes share too many switching elements, then crosstalk introduced at those switching elements degrades signal quality. Vaez and Lea (IEEE Trans. Commun. 48:(2)316–323, 2000) introduced a parameter c which is the maximum number of distinct switching elements a route can share with other routes in the network. This is called the general crosstalk constraint. This paper presents a new method of analyzing strictly nonblocking multi-log networks under this general crosstalk constraint using linear programming duality.     

Minimum d-blockers and d-transversals in graphs

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property ℘. A d-transversal is a subset of V which intersects any optimum solution in at least d elements while a d-blocker is a subset of V whose removal deteriorates the value of an optimum solution by at least d. We present some general characteristics of these problems, we review some situations which have been studied (matchings, s–t paths and s–t cuts in graphs) and we study d-transversals and d-blockers of stable sets or vertex covers in bipartite and in split graphs.     

The orbit problem is in the GapL hierarchy

The Orbit problem is defined as follows: Given a matrix A∈ℚ ^n×n and vectors x,y∈ℚ ⁿ , does there exist a non-negative integer i such that A ⁱ x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808–821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C₌L with respect to logspace many-one reductions.     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

Minimum entropy coloring

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky (IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem. S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal. G. Joret is a F.R.S.-FNRS Research Fellow.     

Accountability and value for money: a theoretical framework for the relationship in public–private partnerships

There is an implicit assumption in the UK Treasury’s publications on public-private partnerships (PPP)—also more commonly known in the United Kingdom as private finance initiative (PFI)—that accountability and value for money (VFM) are related concepts. While recent academic studies on PPP/PFI (from now on as PFI) have focused on VFM, there is a notable absence of studies exploring the ‘presumed’ relationships between accountability and VFM. Drawing on Dubnick’s (Dubnick and Romzek in American public administration, politics and the management of expectations. Macmillan, New York, 1991, Research in public administration. JAI, Greenwich, 1993; Dubnick in Public service ethics and the cultures of blame, 1996, Public sector ethics: finding and implementing values. Routledge, London, 1998, Int J Org Theory Behav 6(3):405–441, 2003, Public Perform Manage Rev 28(3):376–417, 2005; Dubnick and Justice in But can you trust them to be ethical, 2002) framework for accountability and PFI literature, we develop a research framework for exploring potential relationships between accountability and VFM in PFI projects by proposing alternative accountability cultures, processes and mechanisms for PFI. The PFI accountability model is then exposed to four criteria—warrantability, tractability, measurability and feasibility. Our preliminary interviews provide us guidance in identifying some of the cultures, processes and mechanisms indicated in our model which should enable future researchers to test not only the UK Government’s claimed relationships between accountability and VFM using more specific PFI empirical data, but also a potential relationship between accountability and performance in general.     

On the readability of monotone Boolean formulae

Golumbic et al. (Discrete Appl. Math. 154:1465–1477, 2006) defined the readability of a monotone Boolean function f to be the minimum integer k such that there exists an ∧−∨-formula equivalent to f in which each variable appears at most k times. They asked whether there exists a polynomial-time algorithm, which given a monotone Boolean function f, in CNF or DNF form, checks whether f is a read-k function, for a fixed k. In this paper, we partially answer this question already for k=2 by showing that it is NP-hard to decide if a given monotone formula represents a read-twice function. It follows also from our reduction that it is NP-hard to approximate the readability of a given monotone Boolean function f:{0,1} ⁿ →{0,1} within a factor of O(n)\mathcal{O}(n) . We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form, parameterized by the number of terms in the CNF and the maximum size in each term, or more generally the maximum number of variables in the intersection of any constant number of terms. When the variables of the DNF can be ordered so that each term consists of a set of consecutive variables, we give much tighter logarithmic bounds on the readability.     

Average-case competitive analyses for one-way trading

Consider a trader who exchanges one dollar into yen and assume that the exchange rate fluctuates within the interval [m,M]. The game ends without advance notice, then the trader is forced to exchange all the remaining dollars at the minimum rate m. El-Yaniv et al. presented the optimal worst-case threat-based strategy for this game (El-Yaniv et al. 2001). In this paper, under the assumption that the distribution of the maximum exchange rate is known, we provide average-case analyses using all the reasonable optimization measures and derive different optimal strategies for each of them. Remarkable differences in behavior are as follows: Unlike other strategies, the average-case threat-based strategy that minimizes E[OPT/ALG] exchanges little by little. The maximization of E[ALG/OPT] and the minimization of E[OPT]/E[ALG] lead to similar strategies in that both exchange all at once. However, their timing is different. We also prove minimax theorems with respect to each objective function.