An effective discrete dynamic convexized method for solving the winner determination problem

The winner determination problem (WDP) arises in combinatorial auctions. It is known to be NP-hard. In this paper, we propose a discrete dynamic convexized method for solving this problem. We first propose an adaptive penalty function to convert the WDP into an equivalent unconstrained integer programming problem. Based on the structure of the WDP, we construct an unconstrained auxiliary function, which is maximized iteratively using a local search and is updated whenever a better maximizer is found. By increasing the value of a parameter in the auxiliary function, the maximization of the auxiliary function can escape from previously converged local maximizers. To evaluate the performance of the dynamic convexized method, extensive experiments were carried out on realistic test sets from the literature. Computational results and comparisons show that the proposed algorithm improved the best known solutions on a number of benchmark instances.     

Dynamic matchings in left vertex weighted convex bipartite graphs

A left vertex weighted convex bipartite graph (LWCBG) is a bipartite graph \(G=(X,Y,E)\) in which the neighbors of each \(x\in X\) form an interval in \(Y\) where \(Y\) is linearly ordered, and each \(x\in X\) has an associated weight. This paper considers the problem of maintaining a maximum weight matching in a dynamic LWCBG. The graph is subject to the updates of vertex and edge insertions and deletions. Our dynamic algorithms maintain the update operations in \(O(\log ^2{|V|})\) amortized time per update, obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case \(O(k)\) time, where \(k\) is not greater than the cardinality of the maximum weight matching. That achieves the same time bound as the best known solution for the problem of the unweighted version.     

On the performance of mildly greedy players in cut games

We continue the study of the performance of mildly greedy players in cut games initiated by Christodoulou et al. (Theoret Comput Sci 438:13–27, 2012), where a mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than \(1+\epsilon \), for some given \(\epsilon \ge 0\). Hence, in presence of mildly greedy players, the classical concepts of pure Nash equilibria and best-responses generalize to those of \((1+\epsilon )\)-approximate pure Nash equilibria and \((1+\epsilon )\)-approximate best-responses, respectively. We first show that the \(\epsilon \)-approximate price of anarchy, that is the price of anarchy of \((1+\epsilon )\)-approximate pure Nash equilibria, is at least \(\frac{1}{2+\epsilon }\) and that this bound is tight for any \(\epsilon \ge 0\). Then, we evaluate the approximation ratio of the solutions achieved after a \((1+\epsilon )\)-approximate one-round walk starting from any initial strategy profile, where a \((1+\epsilon )\)-approximate one-round walk is a sequence of \((1+\epsilon )\)-approximate best-responses, one for each player. We improve the currently known lower bound on this ratio from \(\min \left\{ \frac{1}{4+2\epsilon },\frac{\epsilon }{4+2\epsilon }\right\} \) up to \(\min \left\{ \frac{1}{2+\epsilon },\frac{2\epsilon }{(1+\epsilon )(2+\epsilon )}\right\} \) and show that this is again tight for any \(\epsilon \ge 0\). An interesting and quite surprising consequence of our results is that the worst-case performance guarantee of the very simple solutions generated after a \((1+\epsilon )\)-approximate one-round walk is the same as that of \((1+\epsilon )\)-approximate pure Nash equilibria when \(\epsilon \ge 1\) and of that of subgame perfect equilibria (i.e., Nash equilibria for greedy players with farsighted, rather than myopic, rationality) when \(\epsilon =1\).     

Scheduling two job families on a single machine with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a single machine. A setup time is needed for a job if it is the first job to be processed on the machine or its processing on the machine follows a job that belongs to another family. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The aim is to find a schedule for all the jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent being bounded by a fixed value \(Q\). Polynomial-time and pseudo-polynomial-time algorithms are designed to solve the problem involving various combinations of regular scheduling objective functions.     

Serve or skip: the power of rejection in online bottleneck matching

We consider the online matching problem, where n server-vertices lie in a metric space and n request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between any request and its server. It has been shown that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new Serve-or-Skip (SoS) bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GriNN(t) and \({{\textsc {Grin}}^*(t)}\). We show that the SoS model of resource augmentation analysis can essentially simulate the doubled-server-capacity model, and then examine the performance of GriNN(t) and \({\textsc {Grin}^*(t)}\).     

Die Bedeutung des Mentalisierungskonzepts für Coaching

For executives it is essential to interact and resolve conflicts in order to gain or maintain a high level of functioning within the organizational structures. Therefore they must be able to understand the intentional mental states of themselves and their interaction partners to ascribe an adequate meaning that allow to react and respond in an appropriate way. This ability is called mantalization. With the help of mentalization-based therapy (MBT) the improvement of mentalization can be accomplished. For this reason the department of Theory and Methodology of Counseling at the university of Kassel explored whether a mentalization-based Coaching inspired by MBT would be useful.     

Der Stand der Coachingforschung: Kernergebnisse der vorliegenden Metaanalysen

The present article provides a quantitative overview of the state of coaching research. It first provides an insight into the status quo of the academic publishing landscape. Afterwards, results of the four meta-analyes that have been published on coaching research up to now are summarized. First, results on the efficacy of coaching or coaching outcomes are presented. Findings for different outcome measures as well as different study designs are reported. Next, results on predictors of coaching success are presented. They include specific features of the coaching process and setting, the coach-coachee-relationship as well as characteristics of coaches and coachees. The article closes with a summary and an assessment of the state of coaching research.     

Führungsstile – Evaluation einer Nebenaufgabe im Development Center

To asses six different leadership styles we employed a questionnaire during the development center in a manufacturing firm. Analysing the questionnaire indicates its reliability, scalability, economy, usefulness and fairness. An explorative factor analysis supports the factorial validity. A content analysis provides evidence that the transformational leadership style is perceived as the most positive and the authoritarian leadership style as the most negative one. Furthermore, we found transformational leadership style positively correlated with an aggregated measure for the competence extraversion.     

Kognitionspsychologische Grundlagen für den Einsatz sprachlicher Bilder in Coaching und Beratung

Metaphors, stories, comparisons, allegories, parables and other kinds of figurative language are very important in dialogical processes between individuals. But there are also some risks in the work with figurative language: Not all pictures or comparisons which came into the mind of the coach are acceptable or understandable for the client. In this article some models and insights of the cognitive psychology for the use of metaphors in coaching and consulting are introduced. Metaphors are seen as the result of processes of analogical reasoning between knowledge domains. It can be shown in which way the use of metaphors helps to bring out new insights or new knowledge.     

An Examination of Public Private Academic Partnerships: Does Program Success Enhance University Performance Outcomes?

In response to a steady decline in State funding, universities have become heavily involved in a variety of public private academic partnerships (PPAPs) in such areas as medical research, business incubation, technological commercialization, continuing professional education, and intercollegiate athletics. Despite this trend, research which examines if such partnerships actually enhance university funding is rare within the public organization literature. Given this, we focus on university intercollegiate athletics programs, which represent one of the largest PPAPs ever undertaken by universities, to examine whether PPAP success can potentially enhance university performance outcomes leading to increased funding levels. Such programs represent a PPAP because public, private, and academic entities all come together to form an organization (division 1 football at the bowl subdivision level) which seeks to benefit all three entities through sharing resources and responsibilities. Study results showed that athletic success positively influenced a variety of university performance outcome variables such as enrollments and endowments. While results indicate that PPAP success can enhance university funding, we also suggest modifications that should enhance the chances that PPAPs will be successful.