Near optimal algorithms for online weighted bipartite matching in adversary model

Bipartite matching is an important problem in graph theory. With the prosperity of electronic commerce, such as online auction and AdWords allocation, bipartite matching problem has been extensively studied under online circumstances. In this work, we study the online weighted bipartite matching problem in adversary model, that is, there is a weighted bipartite graph \(G=(L,R,E)\) and the left side L is known as input, while the vertices in R come one by one in an order arranged by the adversary. When each vertex in R comes, its adjacent edges and relative weights are revealed. The algorithm should irreversibly decide whether to match this vertex to an unmatched neighbor in L with the objective to maximize the total weight of the obtained matching. When the weights are unbounded, the best algorithm can only achieve a competitive ratio \(\varTheta \left( \frac{1}{n}\right) \), where n is the number of vertices coming online. Thus, we mainly deal with two variants: the bounded weight problem in which all weights are in the range \([\alpha , \beta ]\), and the normalized summation problem in which each vertex in one side has the same total weights. We design algorithms for both variants with competitive ratio \(\varTheta \left( \max \left\{ \frac{1}{\log \frac{\beta }{\alpha }},\frac{1}{n}\right\} \right) \) and \(\varTheta \left( \frac{1}{\log n}\right) \) respectively. Furthermore, we show these two competitive ratios are tight by providing the corresponding hardness results.     

Deconstructing bottleneck shiftiness: the impact of bottleneck position on order release control in pure flow shops

Bottleneck shiftiness is an important managerial problem that negatively affects shop floor manageability. It has therefore received much research attention. Yet research has focused on how protective capacity can be used to influence bottleneck shiftiness rather than on assessing its operational impact. The latter is complex to evaluate since changing the degree of bottleneck shiftiness influences utilization, which makes the results of different experimental settings non-comparable. To overcome this problem, we take a different approach. Bottleneck shiftiness is decomposed by investigating its underlying phenomenon: the impact of the bottleneck position. Using simulation, we demonstrate that tighter control can be exercised, and better performance achieved, the further upstream the bottleneck is positioned. It is consequently important to be aware of the direction of the bottleneck shift. If the bottleneck shifts upstream, performance is likely to improve rather than deteriorate as is implicitly assumed in the literature.     

Exemplar or matching: modeling DCJ problems with unequal content genome data

The edit distance under the DCJ model can be computed in linear time for genomes with equal content or with Indels. But it becomes NP-Hard in the presence of duplications, a problem largely unsolved especially when Indels (i.e., insertions and deletions) are considered. In this paper, we compare two mainstream methods to deal with duplications and associate them with Indels: one by deletion, namely DCJ-Indel-Exemplar distance; versus the other by gene matching, namely DCJ-Indel-Matching distance. We design branch-and-bound algorithms with set of optimization methods to compute exact distances for both. Furthermore, median problems are discussed in alignment with both of these distance methods, which are to find a median genome that minimizes distances between itself and three given genomes. Lin–Kernighan heuristic is leveraged and powered up by sub-graph decomposition and search space reduction technologies to handle median computation. A wide range of experiments are conducted on synthetic data sets and real data sets to exhibit pros and cons of these two distance metrics per se, as well as putting them in the median computation scenario.     

Free or bundled: Channel selection decisions under different power structures

The smart phone industry has unique supply chain relationships. Companies at all levels of the supply chain compete and coordinate with each other for market share and profit. This paper examines the impact of power structures on the decision of pricing and channel selection between a free channel and a bundled channel. We investigate the smart phone supply chain that consists of a handset manufacturer and a telecom service operator. Based on game theory models, the manufacturer׳s optimal retail pricing policies in free and bundled channels and the telecom service operator׳s optimal subsidy policies in a bundled channel are derived under different power structures. It is demonstrated that the firm that has higher channel power will gain more profit, and the smart phone supply chain׳s profit in a Vertical Nash (VN) power structure is higher than that in Telecom Service Operator-Stackelberg (TS) and Manufacturer-Stackelberg (MS) power structures. It is also shown that the smart phone supply chain will choose a bundled channel in TS and MS power structures under certain conditions and will select a free channel in a VN power structure.     

Polynomially solvable special cases of the quadratic bottleneck assignment problem

Quadratic bottleneck assignment problems (QBAP) are obtained by replacing the addition of cost terms in the objective function of a quadratic (sum) assignment problem by taking their maximum. Since the QBAP is an NP\mathcal{NP}-hard problem, polynimially solvable special cases of the QBAP are of interest. In this paper we specify conditions on the cost matrices of QBAP leading to special cases which can be solved to optimality in polynomial time. In particular, the following three cases are discussed: (i) any permutation is optimal (constant QBAP), (ii) a certain specified permutation is optimal (constant permutation QBAP) and (iii) the solution can be found algorithmically by a polynomial algorithm. Moreover, the max-cone of bottleneck Monge matrices is investigated, its generating matrices are identified and it is used as a tool in proving polynomiality results.     

Surviving grief: An analysis of the exchange of hope in online grief communities

Online grief communities represent relatively new forms of peer support. However, the degree to which they are helpful for individual grieving processes is unknown. To date, no research has evaluated the type or quality of support exchanged in online grief communities. To begin to address these questions, this study analyzed 564 messages from internet grief websites to: (1) classify the type of helping skills used, and (2) extract themes contained in the content of the messages. Messages selected for analysis were the first response to an original post, assuming they would be the first effort to provide support to a grieving individual. Results revealed a majority of responses contained self-disclosure. Themes in the messages suggested provision of more than "one-way" support; messages themes also included exchanging hope for the future by sharing one's own story, validating the grief experience, providing resources, and exchanging psychosocial support. Clinical implications and research recommendations are discussed.     

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) \).     

CEO self-discipline in power use: A key moderator for the effect of CEO power

The effect of CEO power depends ultimately on how it is used (i.e., a CEO’s approach to power use), which may vary from one CEO to another. Notwithstanding extensive research on the effect of CEO power on organizational outcomes, researchers have thus far paid very limited attention to how the effect depends on individual differences. In this study I propose a new construct of CEO self-discipline in power use—defined as a CEO’s appeared conformance to the prescribed leadership norms (in particular, norms regarding how leaders should use their power)—and examine how it moderates the effect of CEO power. With a longitudinal dataset from the U.S. computer hardware and software industries, I found that CEO self-discipline in power use weakened the positive effect of CEO power on performance extremeness and improved the effect of CEO power on firm performance.     

安徽财政管理创新

从宿迁到昆明,仇和一路走来,而新闻媒体中的仇和、市民话语中的仇和与真实的仇和等不同影像,在这个过程中相互交织与叠加.自从就任云南省委常委、昆明市委书记,仇和用一种"旋风式"的执政方式搅动起这座"软绵绵"的西南城市.     

O2O在线回收企业再售策略研究

研究了O2O在线回收企业再售策略选择问题。研究发现:当制造商单位产品生产成本和处理商单位产品回收价格较低时,在线回收企业采取全部再售策略;当处理商单位产品回收价格居中时,在线回收企业采取部分再售策略;当处理商单位产品回收价格较高时,采取无再售策略。相对无再售行为的传统第三方回收而言,再售策略下O2O在线回收企业利润较优,故在线回收企业有动力进行再售,并且再售策略下消费者剩余优于传统第三方回收,而制造商利润降低。此外,全部再售策略下在线回收企业废旧品回收量优于传统第三方回收,有助于提升产品利用率,保护环境。     

The problem of demand effects in power studies: Moving beyond power priming

Power in experimental research has been commonly induced by methods that raise concerns regarding demand effects. In this paper, we investigate the empirical relevance of these concerns. In an incentivized online study (N = 1632), we manipulated the method of power manipulation (power priming vs. resource allocation), the level of power (high-power vs. control), and the presence of a manipulation check after the power manipulation. We then assessed risk-taking as an outcome variable in two ways, once as a non-consequential measure (self-report measure) and twice as a consequential measure (incentivized behavioral choices). Our results show that both using power priming (vs. resource allocation) and implementing a manipulation check substantially increased the potential for demand effects as measured by the proportion of participants who were aware of the study hypothesis. In addition, we were able to replicate the positive effect of power on risk-taking previously reported in the literature. However, we only found a significant (and small) effect for our non-consequential measure of risk-taking; when risk-taking was measured with either of our two consequential measures, power had no significant impact. Our pattern of results shows that concerns about demand effects in priming studies cannot be dismissed. We advise researchers, especially those studying power, to steer away from demand-prone manipulations of power and to measure outcome variables (e.g., behavior) through consequential choices.     

Breaking bad online: A synthesis of the darker sides of social networking sites

This essay deconstructs the ultra-dark side of social media and explores the variety of ‘bad’ behaviour online by looking at a wide spectrum of exploitative practices. Through the use of primary data from an online platform, we posit the question ‘What’s the worst thing you’ve done online’? We collect, code and synthesise the fully anonymised discussions and develop a classification model for bad online behaviour. We combine the categories that emerge from our empirical data with those proposed by Baccarella, Wagner, Kietzmann, and McCarthy (2018) and develop a new combined (meta-) classification model that captures both the dark side of social networking and the ultra-dark. A framework is proposed for conceptualising the spectrum of exploitative practices and the essay concludes by providing a series of management considerations.     

第三方电子交易平台的双边市场特征——基于在线个人借贷市场的实证分析

以Prosper在线个人借贷平台为研究对象,实证考察了第三方电子交易市场中用户的交叉网络外部性、自网络外部性和平台定价策略对双边用户效用和平台利润的影响.结果表明:受市场供小于求、平台运营模式和借贷双方交易行为的影响,新借入者规模对借出者收入、前期借出者总规模对借入者需求均产生了显著的正交叉网络外部性;借入者之间由于竞争存在负自网络外部性,而借出者之间由于协同关系存在正自网络外部性;借贷双方对平台交易费具有显著的负价格弹性,平台利润与借贷双方的交易费分别呈现二次线性关系;在市场供小于求的情况下,平台利润主要受到借出者规模及其费率的影响.     

充分发挥政府公报为发展大局服务的作用

政府公报作为面向社会公开发行的政府出版物,传达政令、宣传政策、指导工作、服务社会既是其办刊宗旨,又是其基本职能。回顾政府公报的发展历程,其间经过多次改革和完善。时至今日,政府公报的内容、形式、方式等基本形成了一种定式,长此以往,难免会陷入因循守旧的怪圈。要使政府公报在经济社会发展中发挥更大的作用,必须不断转变观念、创新思路、挖掘潜能,认真研究并解决新形势带来的新课题、新任务。一、法治政府建设的全力推进为政府公报提供了更新的内容,政府公报要在推行政务公开上有所拓展当前,各级政府围绕建设法治政府的目标,大力开…