Exact and approximation algorithms for?the?complementary maximal strip recovery problem

Given two genomic maps G ₁ and G ₂ each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G ₁ and G ₂ such that the resultant subsequences, denoted as $G_{1}^{*}$ and $G_{2}^{*}$ , can be partitioned into the same set of maximal substrings of length greater than or equal to two. Such substrings can occur in the reversal and negated form. The complementary maximal strip recovery (CMSR) problem is to delete the minimum number of markers from both G ₁ and G ₂ for the same purpose, with its optimization goal exactly complementary to maximizing the total number of gene markers retained in the final maximal substrings. Both MSR and CMSR have been shown NP-hard and APX-hard. A?4-approximation algorithm is known for the MSR problem, but no constant ratio approximation algorithm for CMSR. In this paper, we present an O(3 ^k n ²)-time fixed-parameter tractable (FPT) algorithm, where k is the size of the optimal solution, and a 3-approximation algorithm for the CMSR problem.     

Random restricted matching and lower bounds for?combinatorial optimization

We prove results on optimal random extensions of trees over points in [0,1] ^d . As an application, we give a general framework for translating results from combinatorial optimization about the behaviour of random points into results for point sets with sufficiently high regularity. We furthermore introduce a new irregularity problem concerning Voronoi cells, which has applications in logistics.     

Exact closed-form solutions for “optimal inventory model for items with imperfect quality and shortage backordering”

Wee et al. [Optimal inventory model for items with imperfect quality and shortage backordering. Omega 2007;35(1):7–11] recently contributed an optimal inventory model for items with imperfect quality and shortage backordering. This article revisits their study and applies the well-known renewal-reward theorem to obtain a new expected net profit per unit time. We derive the exact closed-form solutions to determine the optimal lot size, backordering quantity and maximum expected net profit per unit time, specifically without differential calculus. We also solve the same model algebraically from another direction, which has been mentioned, but the process has not been finished yet. The problem parameter effects upon the optimal solutions are examined analytically and numerically.     

Comment on “Approximation algorithms for quadratic programming”

Journal of Combinatorial Optimization - The radius of the outer Dikin ellipsoid of the intersection of m ellipsoids due to Fu et al. (J. Comb. Optim., 2, 29-50, 1998) is corrected from m to...     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Why do users trust algorithms? A review and conceptualization of initial trust and trust over time

Algorithms are increasingly playing a pivotal role in organizations' day-to-day operations; however, a general distrust of artificial intelligence-based algorithms and automated processes persists. This aversion to algorithms raises questions about the drivers that lead managers to trust or reject their use. This conceptual paper aims to provide an integrated review of how users experience the encounter with AI-based algorithms over time. This is important for two reasons: first, their functional activities change over the course of time through machine learning; and second, users' trust develops with their level of knowledge of a particular algorithm. Based on our review, we propose an integrative framework to explain how users’ perceptions of trust change over time. This framework extends current understandings of trust in AI-based algorithms in two areas: First, it distinguishes between the formation of initial trust and trust over time in AI-based algorithms, and specifies the determinants of trust in each phase. Second, it links the transition between initial trust in AI-based algorithms and trust over time to representations of the technology as either human-like or system-like. Finally, it considers the additional determinants that intervene during this transition phase.     

Complexity analysis for maximum flow problems with arc reversals

We provide a comprehensive study on network flow problems with arc reversal capabilities. The problem is to identify the arcs to be reversed in order to achieve a maximum flow from source(s) to sink(s). The problem finds its applications in emergency transportation management, where the lanes of a road network could be reversed to enable flow in the opposite direction. We study several network flow problems with the arc reversal capability and discuss their complexity. More specifically, we discuss the polynomial time algorithms for the maximum dynamic flow problem with arc reversal capability having a single source and a single sink, and for the maximum (static) flow problem. The presented algorithms are based on graph transformations and reductions to polynomially solvable flow problems. In addition, we show that the quickest transshipment problem with arc reversal capability and the problem of minimizing the total cost resulting from arc switching costs are NP\mathcal{NP} -hard.     

The bandpass problem: combinatorial optimization and library of problems

A combinatorial optimization problem, called the Bandpass Problem, is introduced. Given a rectangular matrix A of binary elements {0,1} and a positive integer B called the Bandpass Number, a set of B consecutive non-zero elements in any column is called a Bandpass. No two bandpasses in the same column can have common rows. The Bandpass problem consists of finding an optimal permutation of rows of the matrix, which produces the maximum total number of bandpasses having the same given bandpass number in all columns. This combinatorial problem arises in considering the optimal packing of information flows on different wavelengths into groups to obtain the highest available cost reduction in design and operating the optical communication networks using wavelength division multiplexing technology. Integer programming models of two versions of the bandpass problems are developed. For a matrix A with three or more columns the Bandpass problem is proved to be NP-hard. For matrices with two or one column a polynomial algorithm solving the problem to optimality is presented. For the general case fast performing heuristic polynomial algorithms are presented, which provide near optimal solutions, acceptable for applications. High quality of the generated heuristic solutions has been confirmed in the extensive computational experiments. As an NP-hard combinatorial optimization problem with important applications the Bandpass problem offers a challenge for researchers to develop efficient computational solution methods. To encourage the further research a Library of Bandpass Problems has been developed. The Library is open to public and consists of 90 problems of different sizes (numbers of rows, columns and density of non-zero elements of matrix A and bandpass number B), half of them with known optimal solutions and the second half, without.     

Preparing for business model change: the “pre-stage” finding

The purpose of this paper is to investigate managers’ initiatives in the context of an emergent technology and their effect on the business models of firms. Building on four case studies of organizations interested in using an emergent technology for commercial purposes, this study applies a process-based framework of business model change. The main finding is that managers’ initiatives occur in the context of a “pre-stage” of potential business model change, which includes processes of experimenting and learning. The pre-stage finding gives a better understanding of when change initiatives affect a business model and when they do not, allowing managers to adopt a more proactive behaviour and guide their organizations towards effective business model change. The main contribution of this paper is to suggest the inclusion of the pre-stage idea in research and practice, since it is an intermediary step in the process of business model change that has been overlooked.     

Algebraic and combinatorial properties of ideals and algebras of uniform clutters of TDI systems

Let \(\mathcal{C}\) be a uniform clutter and let A be the incidence matrix of \(\mathcal{C}\). We denote the column vectors of A by v ₁,…,v _q . Under certain conditions we prove that \(\mathcal{C}\) is vertex critical. If \(\mathcal{C}\) satisfies the max-flow min-cut property, we prove that A diagonalizes over ? to an identity matrix and that v ₁,…,v _q form a Hilbert basis. We also prove that if \(\mathcal{C}\) has a perfect matching such that \(\mathcal{C}\) has the packing property and its vertex covering number is equal to 2, then A diagonalizes over ? to an identity matrix. If A is a balanced matrix we prove that any regular triangulation of the cone generated by v ₁,…,v _q is unimodular. Some examples are presented to show that our results only hold for uniform clutters. These results are closely related to certain algebraic properties, such as the normality or torsion-freeness, of blowup algebras of edge ideals and to finitely generated abelian groups. They are also related to the theory of Gröbner bases of toric ideals and to Ehrhart rings.     

Computing unique maximum matchings in $$$$ time for König–Egerváry graphs and unicyclic graphs

Let \(\alpha \left( G\right) \) denote the maximum size of an independent set of vertices and \(\mu \left( G\right) \) be the cardinality of a maximum matching in a graph \(G\). A matching saturating all the vertices is a perfect matching. If \(\alpha \left( G\right) +\mu \left( G\right) =\left| V(G)\right| \), then \(G\) is called a König–Egerváry graph. A graph is unicyclic if it is connected and has a unique cycle. It is known that a maximum matching can be found in \(O(m\cdot \sqrt{n})\) time for a graph with \(n\) vertices and \(m\) edges. Bartha (Proceedings of the 8th joint conference on mathematics and computer science, Komárno, Slovakia, 2010) conjectured that a unique perfect matching, if it exists, can be found in \(O(m)\) time. In this paper we validate this conjecture for König–Egerváry graphs and unicylic graphs. We propose a variation of Karp–Sipser leaf-removal algorithm (Karp and Sipser in Proceedings of the 22nd annual IEEE symposium on foundations of computer science, 364–375, 1981) , which ends with an empty graph if and only if the original graph is a König–Egerváry graph with a unique perfect matching (obtained as an output as well). We also show that a unicyclic non-bipartite graph \(G\) may have at most one perfect matching, and this is the case where \(G\) is a König–Egerváry graph.     

Optimal on-line algorithms for one batch machine with grouped processing times

In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+φ)p], where p>0 and \(\phi=(\sqrt{5}-1)/2\). Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio \((\sqrt{5}+1)/2\) are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio \((\sqrt{5}+1)/2\). The two class of algorithms are optimal for the problems studied here.     

Approximation algorithms for multicast routing in ad hoc wireless networks

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.     

The prospect for petrochemicals—merger and rationalization?

The petrochemical industry is an international industry subject to global competition by regional blocks. This aspect must always be borne in mind when considering the industry's future. As far as producing base chemicals is concerned, oil is likely to remain a major feedstock for many years to come. That is not to say that it will not become increasingly short and for this and other production reasons closer links are likely to be developed between chemical manufacturers and oil producers and refiners—be they countries or companies. With escalating energy and labour costs there must be a greater concentration on increasing production efficiency and reducing process costs. The industry must be prepared to employ the latest technology whenever possible and there will be continuing development of more sophisticated chemical products and applications. There may well be the emergence in Western Europe of more distinct speciality and commodity chemical producers with rationalization occuring by specialization rather than broadening mergers.     

Working shifts—different effects for women and men?

Abstract

Results are reported of a survey on the effects of shiftwork on women and men working rotating shifts under comparable job conditions. Discriminant analyses revealed that gender-related effects of shiftwork could not be found. However, off-the-job work stress, e.g. a gender-related unequal division of domestic duties, clearly differentiated between women and men and the presence or absence of children in the house. The ‘double burden’ for women, in particular for those with children, did not result in more severe psychosocial or subjective health impairments.     

Accountability in Voluntary Partnerships: To Whom and for What?

This paper contributes to the understanding of accountability in collaborative governance by presenting views of practitioners from partnerships formed between K-12 public schools and private and nonprofit organizations in the United States. It focuses on two questions: what do partnership practitioners see the partnerships as being accountable for? And to whom do they see the partnerships as being accountable? The findings suggest that partnership participants reveal more of client-based and results-oriented views of accountability. They are more directly concerned about professional accountability and accountability to the partners. A concentric-circles model is then developed to illustrate the accountability relationships in partnerships.     

Contingencies or cognitions? Two paths for research on organization and technology

This article reviews and criticizes the treatment of the concepts of technology in organization theories. It pays special attention to how authors of the contingency school interpret empirical results concerning relationships between technology and organization structure. When authors have encountered contradictory results, they attempt to find flaws in previous research and to ask for methodologically more precise research. As this way of dealing with anomalies yields little fruit in the long run, organization theorists need new frameworks for investigating the significance of technology for the design of organizations. An actor-oriented approach can frame investigations into the cognitive processes dissolving or modifying the relationships.     

HRD standards and standardization: where now for human resource development?

This paper examines standard-setting and standardization processes currently being undertaken in the human resources field and makes a ‘call to action’ for human resource development (HRD) scholars and practitioners to influence these developments. The paper provides a reflexive ‘insider account’ of HR standards development combining personal experience with theoretical perspectives; ‘grey’ and practitioner literatures; and secondary data sources. Drawing on scholarly literature sources, opportunities and dilemmas of standardization processes in the HR field are discussed. Grounded in the standardization literature, alternative approaches to system-wide (meta) standards are identified. Drawing on publically available information, different standardization approaches in USA and UK are discussed. The paper critiques the dominant performance-orientated paradigm and ‘rules-based’ approach to standards and argues for an alternative, principles-based approach for HR standardization to support sustainable individual and organizational performance. These issues have important consequences for HRD identity, pedagogy, education, and practice. In addition to the development of an original typology of emerging HR standardization, the paper contributes a new perspective to debates about the identity, values, purpose, and contribution of HRD and the relationship between HRD and human resource management (HRM).     

Organization and Work Situations: Which sources for the learning process?

ABSTRACT: The observation of economic activity grants an equally important place to learning as some recent theoretical problems. However, what is meant by learning, and what in the productive activity enables the application of the learning process? This paper examines the notion of learning, as far as the firm is concerned, putting the emphasis on two main directions. On one hand, learning is not only a dynamic but also a process: it is not only a matter of going from one point to another, but also a process of construction of knowledge and rules. On the other hand, this process must be understood as an articulation between individual and organizational learning.     

What Management Style is Considered Best for a Team-Based Organization and Why?

The paper reviews various styles of management that are commonly employed for managing team-based programs and projects in many manufacturing industries. It analyzes the characteristics of each style with respect to the needs for decomposing the goals into smaller chunks in a team-based organization or in a program. Three styles of management were considered at Electronic Data Systems (EDS) for this analysis. Based on the experiences of applying each style during various team-based programs at EDS, Ford Motor Company, General Motors, and Unigraphics Solutions accounts and from the varying degree of success achieved then, the paper points out which management style is well suited for managing this decomposed set of goals and why. It then analyzes which style is best suited for managing a team-based organization. As W. Edward Deming said in his book The New Economics, setting a particular numerical goal accomplishes nothing. Setting a method to achieve a common set of consistent goals is important. Clear and consistent set of decomposed goals provides a `constancy-of-purpose.' Without a common subset of consistent goals identified for each concurrent team (decomposed from its original sets), the product development teams do not know what is expected from each other and how to accomplish the tasks concurrently. Finally, the paper discusses why a management style, which is based on a set of constancy-of-purpose (governing) principles, is considered superior for managing a team-based organization.