Corrigendum to “Shifting : one-inclusion mistake bounds and sample compression” [J. Comput. System Sci. 75 (1) (2009) 37–59]

H. Simon and B. Szörényi have found an error in the proof of Theorem 52 of “Shifting: One-inclusion mistake bounds and sample compression”, Rubinstein et al. (2009). In this note we provide a corrected proof of a slightly weakened version of this theorem. Our new bound on the density of one-inclusion hypergraphs is again in terms of the capacity of the multilabel concept class. Simon and Szörényi have recently proved an alternate result in Simon and Szörényi (2009).

Shifting : one-inclusion mistake bounds and sample compression

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy. The key step in their proof is a d=VC(F) bound on the graph density of a subgraph of the hypercube—one-inclusion graph. The first main result of this report is a density bound of n∙choose(n-1,≤d-1)/choose(n,≤d) < d, which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension d as being d-contractible simplicial complexes, extending the well-known characterization that d=1 maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth—the second part to a conjectured proof of correctness for Peeling—that every class has one-inclusion minimum degree at most its VC-dimension. Our final main result is a k-class analogue of the d/n mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of O(log n) and is shown to be optimal up to a O(log k) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout

Politics and school education in Australia : a case of shifting purposes

Purpose – The paper aims to argue that there has been a privileging of the private (social mobility) and economic (social efficiency) purposes of schooling at the expense of the public (democratic equality) purposes of schooling. Design/methodology/approach – The paper employs a literature review, policy and document analysis. Findings – Since the late 1980s, the schooling agenda in Australia has been narrowed to one that gives primacy to purposes of schooling that highlight economic orientations (social efficiency) and private purposes (social mobility). Practical implications – The findings have wider relevance beyond Australia, as similar policy agendas are evident in many other countries raising the question as to how the shift in purposes of education in those countries might mirror those in Australia. Originality/value – While earlier writers have examined schooling policies in Australia and noted the implications of managerialism in relation to these policies, no study has analysed these policies from the perspective of the purposes of schooling. Conceptualising schooling, and its purposes in particular, in this way refocuses attention on how societies use their educational systems to promote (or otherwise) the public good.

Multiculturalism, education for sustainable development (ESD) and the shifting discursive landscape of social inclusion

Australia has a long and sometimes turbulent relationship with the migrant Other. This paper examines a component of this relationship via the window of contemporary multicultural policy. The paper begins with an analysis of the political and social conditions that enabled a national and bipartisan policy of multiculturalism to emerge as formalised federal policy during the late 1960s and early 1970s. The paper re-problematises the influences that helped shape Australia's articulation of race and ethnicity and argues that multiculturalism, within a post-September 11 environment, can no longer be framed solely within its traditional framework of social justice. The paper positions education for sustainable development (ESD) as an emerging discursive field that provides educators with an alternative road map for critiquing Australia's fluid relationship with the migrant Other. By linking the tenets of multiculturalism with ESD, this paper suggests pre-service teacher educators are presented with a productive, and at the same time politically palatable, means for regaining pedagogical traction for a semi-dormant agenda of social inclusion.

International law and the regulation of violence : shifting perceptions of the legitimacy of the jus ad bellum?

International law’s capacity to influence state behaviour by regulating recourse to violence has been a longstanding source of debate among international lawyers and political scientists. On the one hand, sceptics assert that frequent violations of the prohibition on the use of force have rendered article 2(4) of the UN Charter redundant. They contend that national self-interest, rather than international law, is the key determinant of state behaviour regarding the use of force. On the other hand, defenders of article 2(4) argue first, that most states comply with the Charter framework, and second, that state rhetoric continues to acknowledge the existence of the jus ad bellum. In particular, the fact that violators go to considerable lengths to offer legal or factual justifications for their conduct – typically by relying on the right of self-defence – is advanced as evidence that the prohibition on the use of force retains legitimacy in the eyes of states. This paper identifies two potentially significant features of state practice since 2006 which may signal a shift in states’ perceptions of the normative authority of article 2(4). The first aspect is the recent failure by several states to offer explicit legal justifications for their use or force, or to report action taken in self-defence to the Security Council in accordance with Article 51. Four incidents linked to the global “war on terror” are examined here: Israeli airstrikes in Syria in 2007 and in Sudan in 2009, Turkey’s 2006-2008 incursions into northern Iraq, and Ethiopia’s 2006 intervention in Somalia. The second, more troubling feature is the international community’s apparent lack of concern over the legality of these incidents. Each use of force is difficult to reconcile with the strict requirements of the jus ad bellum; yet none attracted genuine legal scrutiny or debate among other states. While it is too early to conclude that these relatively minor incidents presage long term shifts in state practice, viewed together the two developments identified here suggest a possible downgrading of the role of international law in discussions over the use of force, at least in conflicts linked to the “war on terror”. This, in turn, may represent a declining perception of the normative authority of the jus ad bellum, and a concomitant admission of the limits of international law in regulating violence.

A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version SBP algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: i) a topological-sequence algorithm is proposed to decompose the PMJSS problem into a set of single-machine scheduling (SMS) and/or parallel-machine scheduling (PMS) subproblems; ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; iii) the Jackson rule is extended to solve the PMS subproblem; iv) a Tabu Search metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.

Shifting meanings : The role of metaphors in collective meaning–making in complex project leadership

This paper examines the use of metaphors in collective meaning-making in the work of managers and leaders of megaprojects, drawing on interviews with thirty-three leaders of complex projects in a case study organisation responsible for the delivery of major acquisitions. Recognising the notion of both contextualised and decontextualised approaches to either seeking to elicit or project metaphors, the paper describes the various ways in practising project leaders describe their work and the synergies these metaphors have with the broader social discourse and theorisation around complexity and the language of complex adaptive systems. The paper presents our case study findings where we outline our typology of meta-metaphors describing project leaders’ multiple roles and our interpretation of the significance of these choices.

Shifting the Airline Business Model - Current Struggles of National Carriers to Become Profitable Passenger Experience Companies

National flag carriers are struggling for survival, not only due to classical reasons such as increase in fuel and tax or natural disasters, but largely due to the inability to quickly adapt to its competitive environment – the emergence of budget and Persian Gulf airlines. In this research, we investigate how airlines can transform their business models via technological and strategic capabilities to become profitable and sustainable passenger experience companies. To formulate recommendations, we analyze customer sentiments via social media to understand what people are saying about the airlines.

Shifting global powers and international law : challenges and opportunities [Challenges of Globalisation series]

This book examines the influence of emerging economies on international legal rules, institutions and processes. It describes recent and predicted changes in economic, political and cultural powers, flowing from the growth of emerging economies such as China, India, Brazil, South Africa and Russia, and analyses the influence of these changes on various legal frameworks and norms. Its contributors come from a variety of fields of expertise, including international law, politics, environmental law, human rights, economics and finance. The book begins by providing a broad analysis of the nature of the shifting global dynamic in its historical and contemporary contexts, including analysis of the rise of China as a major economic and political power and the end of the period of United States domination in international affairs. It illustrates the impact of these changes on states’ domestic policies and priorities, as they adapt to a new international dynamic. The authors then offer a range of perspectives on the impact of these changes as they relate to specific regimes and issues, including climate change regulation, collective security, indigenous rights, the rights of women and girls, environmental protection and foreign aid and development. The book provides a fresh and comprehensive analysis of an issue with extensive implications for international law and politics.

Evaluating consent and legitimacy amongst shifting community norms : an EVE Online case study

The legitimate resolution of disputes in online environments requires a complex understanding of the social norms of the community. The conventional legal approach to resolving disputes through literal interpretation of the contractual terms of service is highly problematic because it does not take into account potential conflict with community expectations. In this paper we examine the importance of consent to community governance and argue that a purely formal evaluation of consent is insufficient to legitimately resolve disputes. As online communities continue to grow in importance to the lives of their participants, the importance of resolving disputes legitimately, with reference to the consent of the community, will also continue to grow. Real consent, however, is difficult to identify. We present a case study of botting and real money trading in EVE Online that highlights the dynamic interaction of community norms and private governance processes. Through this case study, we argue that the major challenge facing regulators of online environments is that community norms are complex, contested, and continuously evolving. Developing legitimate regulatory frameworks then depends on the ability of regulators to create efficient and acceptable modes of dispute resolution that can take into account (and acceptably resolve) the tension between formal contractual rules and complex and conflicting community understandings of acceptable behaviour.