A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

Pluralism in Organizations: Learning from Unconventional Forms of Organizations

The bureaucratic organization is still regarded as the conventional organizational form, but is ill‐suited to an increasingly pluralistic world. Research on the variety of organizational forms has increased dramatically over the past three decades and offers the potential to understand better how pluralism is manifested and managed within organizations. However, this research remains fragmented. The purpose of this paper is to review and synthesize research on unconventional organizations to explore how organizations resolve or attenuate the tensions related to pluralism. Drawing from research in leading management journals, it covers seven distinct literatures: ‘referent organization’, ‘temporary organization’, ‘pluralistic organization’, ‘meta‐organization’, ‘bridging organization’, ‘hybrid organization’ and ‘field‐configuring event’. For each literature, the authors trace the genealogy of the key concepts and review their distinct insights regarding organizational pluralism. They then synthesize and discuss their collective contributions and conclude with avenues of research for pluralism in organizations.     

Does the capital of social capital matter? Relational resources of the board and the performance of Brazilian companies

Based on theories of social capital, in this study, we seek to assess the impact of a board’s social capital on the market value of companies listed on the Brazilian stock exchange. As our indicator of social capital, we use the relational resources identified in the direct, indirect and heterogeneous ties of the board. Employing panel data from 508 observations, our results indicate that heterogeneous relational resources have a stronger and more significant influence than the resources available from board members’ direct relationships. Additionally, as the effects of board interlock are endogenously determined by several factors related to the firm level, we seek to mitigate the endogeneity problem using models of instrumental variables and simultaneous equations. Our hypotheses were consistent after controlling for endogeneity. We also check whether the board’s social capital could present a U-inverted effect on the market value. This relationship was only plausible in social capital by indirect ties. Finally, we isolate the effect of relational resources within and between industries on Tobin’s Q. There was no significant effect through interlocks within the same industry. However, ties with companies in several other industries were significant.     

On the relationship between compliance with recommendations on the audit committee of codes of good practices and financial reporting quality

Codes of good practices provide a soft alternative to the hard legislation approach to corporate governance. These codes include a set of recommendations that companies are expected to follow in order to enhance governance structures and practices. Some of these recommendations specifically aim to improve the effectiveness of the audit committee. We investigate the relationship between the level of compliance with recommendations on the audit committee of the Spanish Unified Code and financial reporting quality, as measured by discretionary accruals and by the opinion of the audit report. We use a sample of companies listed in the Spanish stock market for the years between 2007 and 2013. Results show a strong and positive relationship between the level of compliance with recommendations and the quality of financial reporting. We also report significant results for some specific recommendations. These results are robust to various checks. Therefore, the level of compliance with recommendations on the audit committee might provide a feasible and reliable indicator of the quality of financial reports released by the company.     

Performance management change in archaeological sites: The case of Herculaneum Conservation Project

This study focuses on the issues relating to the implementation of management accounting systems in complex settings such as archeological sites. The aim is to understand the conditions under which the implementation of performance management systems (PMS) may enable cultural organizations to fulfil their multiple objectives and the factors which play a crucial role in such dynamics. Focusing on the Herculaneum Conservation Project (HCP) the study explains how PMS came to be implemented having been made acceptable to all parties involved. The Middle Range Theory as developed by Broadbent and Laughlin (Accounting control and controlling accounting: interdisciplinary and critical perspectives, Bingley, Emerald, 2013) was utilized to explore how the PMS change took place in the HCP, and focus on the factors influencing this process. The findings reveal that the change in the PMS benefited from the involvement of a multidisciplinary Specialist Work Group. This involvement reduced the natural tendency to resist the forces of change and increased the commitment of the various groups of stakeholders to the new culture. The findings reveal how PMS were developed in the context of a multifaceted approach to change, allowing us to draw both theoretical and practical lessons that may be brought to bear in other complex contexts.     

FPT-algorithms for some problems related to integer programming

This paper studies a new version of the location problem called the mixed center location problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in \(O(n^2\log n)\) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in \(O(n^{m+O(\sqrt{k-m})})\) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem (\(k>2\)).     

A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph \(G=(V,E)\) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in \(O(|E|^2)\) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays

We revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set.     

New bounds for locally irregular chromatic index of bipartite and subcubic graphs

A graph is locally irregular if the neighbors of every vertex v have degrees distinct from the degree of v. A locally irregular edge-coloring of a graph G is an (improper) edge-coloring such that the graph induced on the edges of any color class is locally irregular. It is conjectured that three colors suffice for a locally irregular edge-coloring. In the paper, we develop a method using which we prove four colors are enough for a locally irregular edge-coloring of any subcubic graph admiting such a coloring. We believe that our method can be further extended to prove the tight bound of three colors for such graphs. Furthermore, using a combination of existing results, we present an improvement of the bounds for bipartite graphs and general graphs, setting the best upper bounds to 7 and 220, respectively.