A combinatorial proof for the circular chromatic number of Kneser graphs

Chen (J Combin Theory A 118(3):1062–1071, 2011) confirmed the Johnson–Holroyd–Stahl conjecture that the circular chromatic number of a Kneser graph is equal to its chromatic number. A shorter proof of this result was given by Chang et al. (J Combin Theory A 120:159–163, 2013). Both proofs were based on Fan’s lemma (Ann Math 56:431–437, 1952) in algebraic topology. In this article we give a further simplified proof of this result. Moreover, by specializing a constructive proof of Fan’s lemma by Prescott and Su (J Combin Theory A 111:257–265, 2005), our proof is self-contained and combinatorial.     

A note on the duality between matchings and vertex covers in balanced hypergraphs

We present a new Min-Max theorem for an optimization problem closely connected to matchings and vertex covers in balanced hypergraphs. The result generalizes K?nig’s Theorem (Berge and Las Vergnas in Ann N Y Acad Sci 175:32–40, 1970; Fulkerson et al. in Math Progr Study 1:120–132, 1974) and Hall’s Theorem (Conforti et al. in Combinatorica 16:325–329, 1996) for balanced hypergraphs.     

Note on power propagation time and lower bounds for the power domination number

We present a counterexample to a lower bound for the power domination number given in Liao (J Comb Optim 31:725–742, 2016). We also define the power propagation time, using the power domination propagation ideas in Liao and the (zero forcing) propagation time in Hogben et al. (Discrete Appl Math 160:1994–2005, 2012).     

Smart elements in combinatorial group testing problems

In combinatorial group testing problems the questioner needs to find a special element \(x \in [n]\) by testing subsets of [n]. Tapolcai et al. (in: Proceedings of IEEE INFOCOM, Toronto, Canada, pp 1860–1868, 2014; IEEE Trans Commun 64(6):2527–2538, 2016) introduced a new model, where each element knows the answer for those queries that contain it and each element should be able to identify the special one. Using classical results of extremal set theory we prove that if \(\mathcal {F}_n \subseteq 2^{[n]}\) solves the non-adaptive version of this problem and has minimal cardinality, then

$$\begin{aligned} \lim _{n \rightarrow \infty } \frac{|\mathcal {F}_n|}{\log _2 n} = \log _{(3/2)}2. \end{aligned}$$

This improves results in Tapolcai et al. (2014, 2016). We also consider related models inspired by secret sharing models, where the elements should share information among them to find out the special one. Finally the adaptive versions of the different models are investigated.

     

Competitive analysis of bi-directional non-preemptive conversion

In an online conversion problem a player is converting one asset into another, e.g. dollars to yen, based on a finite sequence of unknown future conversion rates. When a new rate is announced the player must decide how many dollars (yen) to convert to yen (dollars) according to this rate. Conversion is over when the last rate has appeared. The objective is to maximize terminal wealth after conversion. In uni-directional conversion dollars are converted to yen and in bi-directional conversion not only dollars to yen but also yen to dollars may be converted. If all current wealth has to be converted at one rate we call the problem non-preemptive; if parts of the current wealth can be converted at one rate we call it preemptive. We assume that lower and upper bounds on conversion rates are given. Uni-directional preemptive and non-preemptive and bi-directional preemptive conversion is investigated in El Yaniv et al. (Proceeding 33rd annual symposium on foundations of computer science, pp 327–333, 1992, Algorithmica 30:101–139, 2001). Their results for bi-directional preemptive conversion are improved by Dannoura and Sakurai (Inf Process Lett 66:27–33, 1998). The suggested improvement is conjectured not to be optimal for bi-directional preemptive conversion. There are no results for optimal bi-directional non-preemptive conversion. We investigate the problem of bi-directional non-preemptive online conversion. We present lower bounds, upper bounds and an optimal algorithm to solve the problem. Moreover, we prove that the algorithm of Dannoura and Sakurai 1998 is not optimal for bi-directional preemptive conversion.     

Lawler’s minmax cost problem under uncertainty

The well-known \(O(n^2)\) minmax cost algorithm of Lawler (Manag Sci 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We first develop a fast updating algorithm to obtain optimal solutions for two neighboring instances. This method will be used throughout this article. Then we consider job cost functions that depend on the completion time and on one or more additional numerical parameters. The parameters are uncertain and take values from given intervals. Under the uncertainty, we apply the minmax regret criterion for choosing a solution. We generalize results by Brauner et al. (J Sched, 2015) for decomposable cost functions with deterministic processing times and a single uncertain parameter to general cost functions. We describe different conditions, under which minmax regret solutions can be obtained with the time complexity \(O(n^3)\) or \(O(n^2)\). Then the updating algorithm is applied to the lateness model by Kasperski (Oper Res Lett 33:431–436, 2005) where both the processing time and the due date of each job are uncertain. The original \(O(n^4)\) running time is improved to the time complexity \(O(n^3)\). Finally, we extend the cost functions with a single uncertain parameter to those with a vector of additional uncertain parameters, improve one of the complexity results by Volgenant and Duin (Comput Oper Res 37:909–915, 2010) and solve some new problems.     

Optimizing some constructions with bars: new geometric knapsack problems

A set of vertical bars planted on given points of a horizontal line defines a fence composed of the quadrilaterals bounded by successive bars. A set of bars in the plane, each having one endpoint at the origin, defines an umbrella composed of the triangles bounded by successive bars. Given a collection of bars, we study how to use them to build the fence or the umbrella of maximum total area. We present optimal algorithms for these constructions. The problems introduced in this paper are related to the Geometric Knapsack problems (Arkin et al. in Algorithmica 10:399–427, 1993) and the Rearrangement Inequality (Wayne in Scripta Math 12(2):164–169, 1946).     

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.     

Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable

Let \(c_{1},c_{2},\ldots ,c_{k}\) be k non-negative integers. A graph G is \((c_{1},c_{2},\ldots ,c_{k})\)-colorable if the vertex set can be partitioned into k sets \(V_{1},V_{2},\ldots ,V_{k}\) such that for every \(i,1\le i\le k\), the subgraph \(G[V_{i}]\) has maximum degree at most \(c_{i}\). Steinberg (Ann Discret Math 55:211–248, 1993) conjectured that every planar graph without 4- and 5-cycles is 3-colorable. Xu and Wang (Sci Math 43:15–24, 2013) conjectured that every planar graph without 4- and 6-cycles is 3-colorable. In this paper, we prove that every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable, which improves the result of Xu and Wang (Sci Math 43:15–24, 2013), who proved that every planar graph without 4- and 6-cycles is (1, 1, 0)-colorable.     

On Motzkin–Straus type results for non-uniform hypergraphs

Recently, some extensions of Motzkin–Straus theorems were proved for non-uniform hypergraphs whose edges contain 1 or r vertices in Gu et al. (J Comb Optim 31:223–238, 2016), Peng et al. (Discret Appl Math 200:170–175, 2016a), where r is a given integer. It would be interesting if similar results hold for other non-uniform hypergraphs. In this paper, we establish some Motzkin–Straus type results for general non-uniform hypergraphs. In particular, we obtain some Motzkin–Straus type results in terms of the Lagrangian of non-uniform hypergraphs when there exist some edges consisting of 2 vertices in the given hypergraphs. The presented results unify some known Motzkin–Straus type results for both uniform and non-uniform hypergraphs and also provide solutions to a class of polynomial optimization problems over the standard simplex in Euclidean space.     

Improved algorithmic results for unsplittable stable allocation problems

The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is “stable” based on a set of underlying preference lists submitted by the jobs and machines. Building on the initial work of Dean et al. (The unsplittable stable marriage problem, 2006), we study a natural “unsplittable” variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem (McDermid and Manlove in J Comb Optim 19(3): 279–303, 2010). Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed in McDermid and Manlove (J Comb Optim 19(3): 279–303, McDermid and Manlove 2010), we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce “relaxed” unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.     

Towards the price of leasing online

We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an \(O\left( \log (mK)\log n\right) \)-competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an \(O\left( K\log n\right) \)-competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of \(O\left( l_{\text {max}} \log l_{\text {max}} \right) \) (with the maximal lease length \(l_{\text {max}} \)). For many natural problem instances, the bound improves to \(O\left( K^2\right) \).     

Comment on ‘A political economy of accounting standard setting’

This comment raises questions about the appropriateness of the model proposed by Königsgruber (J Manag Gov 14:277–295, 2010) in depicting the politics of the standard-setting process in the context of the very different regulatory contexts in the EU and the US.     

An algorithm for finding a representation of a subtree distance

Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mapping \(d:X\times X \rightarrow \mathbb {R}_+\) is called a subtree distance if there exist a weighted tree T and a family \(\{T_x\mid x \in X\}\) of subtrees of T indexed by the elements in X such that \(d(x,y)=d_T(T_x,T_y)\), where \(d_T(T_x,T_y)\ge 0\) is the distance between \(T_x\) and \(T_y\) in T. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in O\((n^4)\) time. In this paper, we show an O\((n^3)\) time algorithm that finds a representation of a given subtree distance. This results in an O\((n^3)\) time algorithm for deciding whether a given mapping is a subtree distance.     

Tight bounds for NF-based bounded-space online bin packing algorithms

In Zheng et al. (J Comb Optim 30(2):360–369, 2015) modelled a surgery problem by the one-dimensional bin packing, and developed a semi-online algorithm to give an efficient feasible solution. In their algorithm they used a buffer to temporarily store items, having a possibility to lookahead in the list. Because of the considered practical problem they investigated the 2-parametric case, when the size of the items is at most 1 / 2. Using an NF-based online algorithm the authors proved an ACR of \(13/9 = 1.44\ldots \) for any given buffer size not less than 1. They also gave a lower bound of \(4/3=1.33\ldots \) for the bounded-space algorithms that use NF-based rules. Later, in Zhang et al. (J Comb Optim 33(2):530–542, 2017) an algorithm was given with an ACR of 1.4243,  and the authors improved the lower bound to 1.4230. In this paper we present a tight lower bound of \(h_\infty (r)\) for the r-parametric problem when the buffer capacity is 3. Since \(h_\infty (2) = 1.42312\ldots \), our result—as a special case—gives a tight bound for the algorithm-class given in 2017. To prove that the lower bound is tight, we present an NF-based online algorithm that considers the r-parametric problem, and uses a buffer with capacity of 3. We prove that this algorithm has an ACR that is equal to the lower bounds for arbitrary r.     

A solution to an open problem on lower against number in graphs

In Wang (Appl Anal Discret Math 4:207–218, 2010) the problem of finding a sharp lower bound on lower against number of a general graph is mentioned as an open question. We solve the problem by establishing a tight lower bound on lower against number of a general graph in terms of order and maximum degree.     

Finding a contra-risk path between two nodes in undirected graphs

Given an undirected graph with a source node s and a sink node t. The anti-risk path problem is defined as the problem of finding a path between node s to node t with the least risk under the assumption that at most one edge of each path may be blocked. Xiao et al. (J Comb Optim 17:235–246, 2009) defined the problem and presented an \(O(mn+n^2 \log n)\) time algorithm to find an anti-risk path, where n and m are the number of nodes and edges, respectively. Recently, Mahadeokar and Saxena (J Comb Optim 27:798–807, 2014) solved the problem in \(O(m+n \log n)\) time. In this paper, first, a new version of the anti-risk path (called contra-risk path) is defined, which is more effective than an anti-risk path in many networks. Then, an algorithm to find a contra-risk path is presented, which runs in \(O(m+n \log n)\) time.     

A simple approximation algorithm for minimum weight partial connected set cover

Let \(LTQ_n\) be the n-dimensional locally twisted cube. Hsieh and Tu (Theor Comput Sci 410(8–10):926–932, 2009) proposed an algorithm to construct n edge-disjoint spanning trees rooted at a particular vertex 0 in \(LTQ_n\). Later on, Lin et al. (Inf Process Lett 110(10):414–419, 2010) proved that Hsieh and Tu’s spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex \(v(\ne r)\), the paths from v to r in any two trees are internally vertex-disjoint. Shortly afterwards, Liu et al. (Theor Comput Sci 412(22):2237–2252, 2011) pointed out that \(LTQ_n\) fails to be vertex-transitive for \(n\geqslant 4\) and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex in \(LTQ_n\). Although this algorithm can simultaneously construct n ISTs, it is hard to be parallelized for the construction of each spanning tree. In this paper, from a modification of Hsieh and Tu’s algorithm, we present a fully parallelized scheme to construct n ISTs rooted at an arbitrary vertex in \(LTQ_n\) in \({\mathcal O}(n)\) time using \(2^n\) vertices of \(LTQ_n\) as processors.     

Even factors of graphs

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Favaron and Kouider (J Gr Theory 77:58–67, 2014) showed that if a simple graph G has an even factor, then it has an even factor F with \(|E(F)| \ge \frac{7}{16} (|E(G)| + 1)\). This ratio was improved to \(\frac{4}{7}\) recently by  Chen and Fan (J Comb Theory Ser B 119:237–244, 2016), which is the best possible. In this paper, we take the set of vertices of degree 2 (say \(V_{2}(G)\)) into consideration and further strengthen this lower bound. Our main result is to show that for any simple graph G having an even factor, G has an even factor F with \(|E(F)| \ge \frac{4}{7} (|E(G)| + 1)+\frac{1}{7}|V_{2}(G)|\).     

1.61-approximation for min-power strong connectivity with two power levels

Given a directed simple graph \(G=(V,E)\) and a cost function \(c:E \rightarrow R_+\), the power of a vertex \(u\) in a directed spanning subgraph \(H\) is given by \(p_H(u) = \max _{uv \in E(H)} c(uv)\), and corresponds to the energy consumption required for wireless node \(u\) to transmit to all nodes \(v\) with \(uv \in E(H)\). The power of \(H\) is given by \(p(H) = \sum _{u \in V} p_H(u)\). Power Assignment seeks to minimize \(p(H)\) while \(H\) satisfies some connectivity constraint. In this paper, we assume \(E\) is bidirected (for every directed edge \(e \in E\), the opposite edge exists and has the same cost), while \(H\) is required to be strongly connected. Moreover, we assume \(c:E \rightarrow \{A,B\}\), where \(0 \le A < B\). We improve the best known approximation ratio from 1.75 (Chen et al. IEEE GLOBECOM 2005) to \(\pi ^2/6 - 1/36 + \epsilon \le 1.61\) using an adaptation of the algorithm developed by Khuller et al. [SIAM J Comput 24(4):859–872 1995, Discr Appl Math 69(3):281–289 1996] for (unweighted) Minimum Strongly Connected Subgraph.