On (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-relaxed strong edge-coloring of graphs

In this paper, we introduce a new relaxation of strong edge-coloring. Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is an assignment of k colors to the edges of G, such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e assigned the same color as e. The (s, t)-relaxed strong chromatic index, denoted by \({\chi '}_{(s,t)}(G)\), is the minimum number k of an (s, t)-relaxed strong k-edge-coloring admitted by G. This paper studies the (s, t)-relaxed strong edge-coloring of graphs, especially trees. For a tree T, the tight upper bounds for \({\chi '}_{(s,0)}(T)\) and \({\chi '}_{(0,t)}(T)\) are given. And the (1, 1)-relaxed strong chromatic index of an infinite regular tree is determined. Further results on \({\chi '}_{(1,0)}(T)\) are also presented.     

A note on (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-relaxed <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling of graphs

Let \(G=(V, E)\) be a graph. For two vertices u and v in G, we denote \(d_G(u, v)\) the distance between u and v. A vertex v is called an i-neighbor of u if \(d_G(u,v)=i\). Let s, t and k be nonnegative integers. An (s, t)-relaxed k-L(2, 1)-labeling of a graph G is an assignment of labels from \(\{0, 1, \ldots , k\}\) to the vertices of G if the following three conditions are met: (1) adjacent vertices get different labels; (2) for any vertex u of G, there are at most s 1-neighbors of u receiving labels from \(\{f(u)-1,f(u)+1\}\); (3) for any vertex u of G, the number of 2-neighbors of u assigned the label f(u) is at most t. The (s, t)-relaxed L(2, 1)-labeling number \(\lambda _{2,1}^{s,t}(G)\) of G is the minimum k such that G admits an (s, t)-relaxed k-L(2, 1)-labeling. In this article, we refute Conjecture 4 and Conjecture 5 stated in (Lin in J Comb Optim. doi: 10.1007/s10878-014-9746-9, 2013).     

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.     

New algorithms for online rectangle filling with <Emphasis Type="BoldItalic">k</Emphasis>-lookahead

We study the online rectangle filling problem which arises in channel aware scheduling of wireless networks, and present deterministic and randomized results for algorithms that are allowed a k-lookahead for k≥2. Our main result is a deterministic min {1.848,1+2/(k−1)}-competitive online algorithm. This is the first algorithm for this problem with a competitive ratio approaching 1 as k approaches +∞. The previous best-known solution for this problem has a competitive ratio of 2 for any k≥2. We also present a randomized online algorithm with a competitive ratio of 1+1/(k+1). Our final result is a closely matching lower bound (also proved in this paper) of $1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2))$1+1/(\sqrt{k+2}+\sqrt{k+1})^{2}>1+1/(4(k+2)) on the competitive ratio of any randomized online algorithm against an oblivious adversary. These are the first known results for randomized algorithms for this problem.     

On the online multi-agent O–D <Emphasis Type="Italic">k</Emphasis>-Canadian Traveler Problem

In this article, we present new results on the online multi-agent O–D k-Canadian Traveler Problem, in which there are multiple agents and an input graph with a given source node O and a destination node D together with edge costs such that at most k edges are blocked. The blocked edges are not known a priori and are not recoverable. All of the agents are initially located at O. The objective is to find an online strategy such that at least one of the agents finds a route from the initial location O to a given destination D with minimum total cost. We focus on the case where communication among the agents is limited in the sense that some travelers can both send and receive information while the others can only receive information. We formalize the definition of agents’ intelligence by specifying three levels. We introduce two online strategies which utilize higher levels of agents’ intelligence to provide updated lower bounds to this problem. We show that one of our strategies is optimal in both cases with complete and limited communication in the special case of O–D edge-disjoint graphs and highest level of agents’ intelligence.     

On irreducible no-hole <Emphasis Type="Italic">L</Emphasis>(2, 1)-coloring of subdivision of graphs

An L(2, 1)-coloring (or labeling) of a graph G is a mapping \(f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}\) such that \(|f(u)-f(v)|\ge 2\) for all edges uv of G, and \(|f(u)-f(v)|\ge 1\) if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by \(\lambda (G)\), is min {span \(f: f\text {is an }L(2,1)\text {-coloring of } G\}\). If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if \(l\in (0,k)\) and there is no vertex v in G such that \(f(v)=l\). A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from \(\{0,1,\ldots ,k\}\), for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by \(\lambda _{inh}(G)\), is defined as \(\lambda _{inh}(G)=\min ~\{\)span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to \(\mathbb {N}\), the h-subdivision of G, denoted by \(G_{(h)}\), is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that \(G_{(h)}\) is inh-colorable for \(h(e)\ge 2\), \(e\in E(G)\), except the case \(\Delta =3\) and \(h(e)=2\) for at least one edge but not for all. Moreover we find the exact value of \(\lambda _{inh}(G_{(h)})\) in several cases and give upper bounds of the same in the remaining.     

A primal–dual online algorithm for the <Emphasis Type="Italic">k</Emphasis>-server problem on weighted HSTs

In this paper, we show that there is a \(\frac{5}{2}\ell \cdot \ln (1+k)\)-competitive randomized algorithm for the k-sever problem on weighted Hierarchically Separated Trees (HSTs) with depth \(\ell \) when \(n=k+1\) where n is the number of points in the metric space, which improved previous best competitive ratio \(12 \ell \ln (1+4\ell (1+k))\) by Bansal et al. (FOCS, pp 267–276, 2011).     

On the <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling conjecture for brick product graphs

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices u and v in G. An L(2, 1)-labeling of G is a function \(f: V \rightarrow \{0,1,\ldots \}\) such that for any two vertices u and v, \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of f is the difference between the largest and the smallest number in f(V). The \(\lambda \)-number \(\lambda (G)\) of G is the minimum span over all L(2, 1)-labelings of G. In this paper, we conclude that the \(\lambda \)-number of each brick product graph is 5 or 6, which confirms Conjecture 6.1 stated in Li et al. (J Comb Optim 25:716–736, 2013).     

“1+1<2”:政府形象建设“相变”思考

<正>李娜澳网夺冠,是中国体育的大事件;李娜冷脸接受家乡政府巨奖,则是中国社交媒体的大事件。2014年1月28日,李娜在当地政府举办的庆功宴上全程黑脸,甚至在接受80万元奖金时面无表情,在舆论场引发广泛争议。有媒体刊登文章,称湖北省给李娜颁奖是"热脸贴了冷屁股"。舆论由此质疑地方政府拿纳税人的钱奖励运动员,把体育政治化,实际上是扭曲了体育的本质。     

An executive hierarchy analysis of stock options: Does gender matter<Emphasis Type="Italic">?</Emphasis>

This study takes a step forward in addressing the influence of stock options on executive risk-taking behavior, examining the moderating role of the executive hierarchy—CEOs versus non-CEO executives—and the gender effect within these corporate positions. Panel data analysis for matched samples of S&P 1500 listed firms between 2006 and 2011 confirms both hierarchical and gender differences in the relationship between executive stock options (ESOs) and risk taking. The maximum wealth at risk at which risk-increasing behavior changes to risk-reducing behavior—in the inverted U-shaped relationship—is higher for CEOs than for non-CEO executives, while gender differences in the ESO risk-taking effect are stronger at the level of CEOs. Thus, our evidence shows the importance of considering executive’s decision-making freedom (by means of hierarchy) in order to predict risk preferences according to executive gender.     

A linear programming duality approach to analyzing strictly nonblocking <Emphasis Type="Italic">d</Emphasis>-ary multilog networks under general crosstalk constraints

When a switching network topology is used for constructing optical cross-connects, as in the circuit switching case, no two routes are allowed to share a link. However, if two routes share too many switching elements, then crosstalk introduced at those switching elements degrades signal quality. Vaez and Lea (IEEE Trans. Commun. 48:(2)316–323, 2000) introduced a parameter c which is the maximum number of distinct switching elements a route can share with other routes in the network. This is called the general crosstalk constraint. This paper presents a new method of analyzing strictly nonblocking multi-log networks under this general crosstalk constraint using linear programming duality.     

有感于“以&#215;&#215;落实&#215;&#215;”

一看“以&#215;&#215;落实&#215;&#215;”,也许会让人丈二和尚摸不着头脑,其实十分简单,有例为证——     

从&#183;速&#183;处&#183;理

“总书记是百姓的贴心人” 2000年2月19日，新千年第一个元宵节的下午，一辆中巴车穿过广东茂名高州市漫山遍野的荔枝林，停在了高州市根子镇这座小山上的观荔亭旁。     

补锅&#183;风险&#183;分手&#183;点火

不利苗头显露出时,不是简单地扼杀于摇篮之中,反而四处煽风点火,主动将局面导入更加混乱、更加危险的地步。补锅是一门老手艺,补锅匠为客户补锅的时候,一定是拿到破锅先敲三敲,借以判断破损的位置及程度,然后就会和客户商量说:这锅某处有3分长的裂缝,需要将敲它到5分,才方便下手修补,如何?李宗吾据此引申出一个“补锅法”:凡你需要解决任何问题,一定要想方设法先将该问题夸大或搞大,然后再施展各种手段予以解决一