Darwinist connections between the systemness of social organizations and their evolution

Is the systemness of social organizations related to their evolution? This research question has not yet received appropriate attention by the literature on management and organization theory. The author believes that addressing it can constitute a substantive opportunity to understand key intertwined associated processes, such as organizational survival, competitive success/advantage, or failure. In this article, the author attempts to contribute to fill the aforesaid gap adopting a critical Darwinist approach.     

Corporate social responsibility: the organizational view

Designing strategies for corporate social responsibility (CSR)-practice nowadays has become essential for organizations. Notwithstanding, how organizations appear internally in a socially responsible context toward their employees has been insufficiently investigated. This study aims at ascertaining how Internal CSR can be conceptualized as well as how it affects employees’ commitment. To do so, the manifestations of Internal CSR are discussed based on social identity theory and further literature, while the developed research model is checked for suitability through a survey generating 2081 employee responses from an international pharmaceutical company. As one result, it can be stated that the factors proposed to constitute Internal CSR are confirmed. Further, the findings entail the following conclusions: Internal CSR has a notable influence on employees’ Affective Organizational Commitment whilst relatively moderate impacting Normative Organizational Commitment. Additionally, Affective Organizational Commitment adopts a mediating function regarding Normative Organizational Commitment.     

Decoupling in the age of market-embedded morality: responsible gambling in a hybrid organization

This paper contributes to the understanding of hybrid organizations by refining the concept of decoupling as a strategic response to conflicting objectives and institutional expectations (Meyer and Rowan in Am J Soc 83:340–363, 1977). In today’s popular responsibility discourse one notes a hopeful “win–win” ideal that invites attempts, by companies in particular, to realize and balance conflicting values and to strive to fulfil both profit objectives and responsibility objectives. Although institutional theory has long acknowledged the strategic response of decoupling in organizational contexts, the potential of exploring and refining how this concept may be used to analyse strategic responses in the contemporary era of market-embedded morality has yet to be explored (Shamir in Econ Soc 37:1–19, 2008). There are good reasons to do so as the present-day discourse on the relation between the economy and morality offers a new set of options and challenges for legitimately responding to institutional demands. This paper draws on an explanatory, rich ethnographic and longitudinal case study of a Swedish fully state-owned company operating in the post 1990s gambling market. We suggest that contemporary hybrid organizations positioned at the crossroads of bureaucratic and market schemes of organizing, may find themselves in a particularly tight spot and seek legitimacy by decoupling—not only by adopting certain legitimizing structures, but also and increasingly with reference to market-embedded morality, a commoditizing of responsibility in their contested market setting. Based on the case findings, we suggest a distinction between organization-based decoupling and market-based decoupling and propose that market-based decoupling may be attractive to hybrid organizations owing to it being less sensitive to scrutiny and accountability claims. But at the same time, our findings indicate that market-based decoupling poses a risk to hybrid organizations, as it does not offer the same degree of legitimacy with key stakeholders/the general public as organization-based decoupling does.     

Reconstruction of hidden graphs and threshold group testing

Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form “Does a set of elements contain a positive one?”. A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form “Whether a set of vertices induces an edge”. Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2nlg?n,(1+o(1))(nlg?n),2n and 2n queries were proposed, respectively. In this paper we improve them to \((1+o(1))(n\lg n),(1+o(1))(\frac{n\lg n}{2}),n+2\lg n\) and n+lg?n, respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements under a more general setting, in which there are two fixed thresholds ? and u, with ?<u, and the response to a query is positive if the tested subset of elements contains at least u positive elements, negative if it contains at most ? positive elements, and it is arbitrarily given otherwise. For the threshold group testing problem with ?=u?1, we show that p positive elements among n given elements can be determined by using O(plg?n) queries, with a matching lower bound.     

An optimal semi-online algorithm for 2-machine scheduling with an availability constraint

This paper considers a problem of semi-online scheduling jobs on two identical parallel machines with objective to minimize the makespan. We assume there is an unavailable period [B,F] on one machine and the largest job processing time P _max? is known in advance. After comparing B with P _max? we consider three cases, and we show a lower bound of the problem are 3/2, 4/3 and \((\sqrt{5}+1)/2\), respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.     

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.     

On maximum Wiener index of trees and graphs with given radius

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.     

Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F ₁?F ₂?????F _n , where each F _k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F _k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, 2007), we obtain the competitive ratio \(16+8\sqrt{3}+\epsilon\). The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8α?1.     

Approximating <Emphasis Type="Italic">k</Emphasis>-generalized connectivity via collapsing HSTs

An instance of the k -generalized connectivity problem consists of an undirected graph G=(V,E), whose edges are associated with non-negative costs, and a collection \({\mathcal{D}}=\{(S_{1},T_{1}),\ldots,(S_{d},T_{d})\}\) of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ??G connects a demand (S _i ,T _i ) when it contains a path with one endpoint in S _i and the other in T _i . Given an integer parameter k, the goal is to identify a minimum cost subgraph that connects at least k demands in \({\mathcal{D}}\).Alon, Awerbuch, Azar, Buchbinder and Naor (SODA ’04) seem to have been the first to consider the generalized connectivity paradigm as a unified machinery for incorporating multiple-choice decisions into network formation settings. Their main contribution in this context was to devise a multiplicative-update online algorithm for computing log-competitive fractional solutions, and to propose provably-good rounding procedures for important special cases. Nevertheless, approximating the generalized connectivity problem in its unconfined form, where one makes no structural assumptions about the underlying graph and collection of demands, has remained an open question up until a recent O(log?² nlog?² d) approximation due to Chekuri, Even, Gupta and Segev (SODA ’08). Unfortunately, the latter result does not extend to connecting a pre-specified number of demands. Furthermore, even the simpler case of singleton demands has been established as a challenging computational task, when Hajiaghayi and Jain (SODA ’06) related its inapproximability to that of dense k -subgraph.In this paper, we present the first non-trivial approximation algorithm for k-generalized connectivity, which is derived by synthesizing several techniques originating in probabilistic embeddings of finite metrics, network design, and randomization. Specifically, our algorithm constructs, with constant probability, a feasible subgraph whose cost is within a factor of O(n ^2/3?polylog(n,k)) of optimal. We believe that the fundamental approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.     

Estimating hybrid frequency moments of data streams

We consider the problem of estimating hybrid frequency moments of two dimensional data streams. In this model, data is viewed to be organized in a matrix form (A _i,j )_1≤i,j,≤n . The entries A _i,j are updated coordinate-wise, in arbitrary order and possibly multiple times. The updates include both increments and decrements to the current value of A _i,j . The hybrid frequency moment F _p,q (A) is defined as \(\sum_{j=1}^{n}(\sum_{i=1}^{n}{A_{i,j}}^{p})^{q}\) and is a generalization of the frequency moment of one-dimensional data streams.We present the first \(\tilde{O}(1)\) space algorithm for the problem of estimating F _p,q for p∈[0,2] and q∈[0,1] to within an approximation factor of 1±ε. The \(\tilde{O}\) notation hides poly-logarithmic factors in the size of the stream m, the matrix size n and polynomial factors of ε ^?1. We also present the first \(\tilde{O}(n^{1-1/q})\) space algorithm for estimating F _p,q for p∈[0,2] and q∈(1,2].     

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

A path in a vertex-colored graph is called a vertex-monochromatic path if its internal vertices have the same color. A vertex-coloring of a graph is a monochromatic vertex-connection coloring (MVC-coloring for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph G, the monochromatic vertex-connection number, denoted by mvc(G), is defined to be the maximum number of colors used in an MVC-coloring of G. These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster (Discrete Math 311:1786–1792, 2011). In this paper, we mainly investigate the Erd?s–Gallai-type problems for the monochromatic vertex-connection number mvc(G) and completely determine the exact value. Moreover, the Nordhaus–Gaddum-type inequality for mvc(G) is also given.     

Erdős–Gallai-type results for colorful monochromatic connectivity of a graph

A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored with one same color. An edge-coloring of G is a monochromatic connection coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices in G. For a connected graph G, the monochromatic connection number of G, denoted by mc(G), is defined to be the maximum number of colors used in an MC-coloring of G. These concepts were introduced by Caro and Yuster, and they got some nice results. In this paper, we study two kinds of Erd?s–Gallai-type problems for mc(G), and completely solve them.     

The connected disk covering problem

Let P be a convex polygon with n vertices. We consider a variation of the K-center problem called the connected disk covering problem (CDCP), i.e., finding K congruent disks centered in P whose union covers P with the smallest possible radius, while a connected graph is generated by the centers of the K disks whose edge length can not exceed the radius. We give a 2.81-approximation algorithm in O(Kn) time.     

Covering directed graphs by in-trees

Given a directed graph D=(V,A) with a set of d specified vertices S={s ₁,…,s _d }?V and a function f : S→? where ? denotes the set of positive integers, we consider the problem which asks whether there exist ∑ _i=1 ^d f(s _i ) in-trees denoted by \(T_{i,1},T_{i,2},\ldots,T_{i,f(s_{i})}\) for every i=1,…,d such that \(T_{i,1},\ldots,T_{i,f(s_{i})}\) are rooted at s _i , each T _i,j spans vertices from which s _i is reachable and the union of all arc sets of T _i,j for i=1,…,d and j=1,…,f(s _i ) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in ∑ _i=1 ^d f(s _i ) and the size of D. Furthermore, for the case where D is acyclic, we present another characterization of the existence of in-trees covering A, and then we prove that in-trees covering A can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs.     

An improved time-space lower bound for tautologies

We show that for all reals c and d such that c ² d<4 there exists a positive real e such that tautologies of length n cannot be decided by both a nondeterministic algorithm that runs in time n ^c , and a nondeterministic algorithm that runs in time n ^d and space n ^e . In particular, for every \(d<\sqrt[3]{4}\) there exists a positive e such that tautologies cannot be decided by a nondeterministic algorithm that runs in time n ^d and space n ^e .     

Safe sets in graphs: Graph classes and structural parameters

A safe set of a graph \(G=(V,E)\) is a non-empty subset S of V such that for every component A of G[S] and every component B of \(G[V {\setminus } S]\), we have \(|A| \ge |B|\) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.     

Two extremal problems related to orders

We consider two extremal problems related to total orders on all subsets of \({\mathbb N}\). The first one is to maximize the Lagrangian of hypergraphs among all hypergraphs with m edges for a given positive integer m. In 1980’s, Frankl and Füredi conjectured that for a given positive integer m, the r-uniform hypergraph with m edges formed by taking the first m r-subsets of \({\mathbb N}\) in the colex order has the largest Lagrangian among all r-uniform hypergraphs with m edges. We provide some partial results for 4-uniform hypergraphs to this conjecture. The second one is for a given positive integer m, how to minimize the cardinality of the union closure families generated by edge sets of the r-uniform hypergraphs with m edges. Leck, Roberts and Simpson conjectured that the union closure family generated by the first m r-subsets of \({\mathbb N}\) in order U has the minimum cardinality among all the union closure families generated by edge sets of the r-uniform hypergraphs with m edges. They showed that the conjecture is true for graphs. We show that a similar result holds for non-uniform hypergraphs whose edges contain 1 or 2 vertices.     

On a general framework for network representability in discrete optimization

In discrete optimization, representing an objective function as an s-t cut function of a network is a basic technique to design an efficient minimization algorithm. A network representable function can be minimized by computing a minimum s-t cut of a directed network, which is an efficiently solvable problem. Hence it is natural to ask what functions are network representable. In the case of pseudo Boolean functions (functions on \(\{0,1\}^n\)), it is known that any submodular function on \(\{0,1\}^3\) is network representable. ?ivný–Cohen–Jeavons showed by using the theory of expressive power that a certain submodular function on \(\{0,1\}^4\) is not network representable. In this paper, we introduce a general framework for the network representability of functions on \(D^n\), where D is an arbitrary finite set. We completely characterize network representable functions on \(\{0,1\}^n\) in our new definition. We can apply the expressive power theory to the network representability in the proposed definition. We prove that some ternary bisubmodular function and some binary k-submodular function are not network representable.     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

On list <Emphasis Type="Italic">r</Emphasis>-hued coloring of planar graphs

A list assignment of G is a function L that assigns to each vertex \(v\in V(G)\) a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper coloring \(\phi \) such that for any vertex v with degree d(v), \(\phi (v)\in L(v)\) and v is adjacent to at least \( min\{d(v),r\}\) different colors. The list r-hued chromatic number of G, \(\chi _{L,r}(G)\), is the least integer k such that for every list assignment L with \(|L(v)|=k\), \(v\in V(G)\), G has an (L, r)-coloring. We show that if \(r\ge 32\) and G is a planar graph without 4-cycles, then \(\chi _{L,r}(G)\le r+8\). This result implies that for a planar graph with maximum degree \(\varDelta \ge 26\) and without 4-cycles, Wagner’s conjecture in [Graphs with given diameter and coloring problem, Technical Report, University of Dortmund, Germany, 1977] holds.