Search

We explore whether training protocols can enhance the ability of social media users to detect fake news, by conducting an online experiment (N = 417) to analyse the effect of such a training protocol, while considering the role of scepticism, age, and level of education. Our findings show a significant relationship between the training protocol and the ability of social media users to detect fake news, suggesting that the protocol can play a positive role in training social media users to recognize fake news. Moreover, we find a direct positive relationship between age and level of education on the one hand and ability to detect fake news on the other, which has implications for future research. We demonstrate the potential of training protocols in countering the effects of fake news, as a scalable solution that empowers users and addresses concerns about the time-consuming nature of fact-checking. [ABSTRACT FROM AUTHOR]

In search problems, a mobile searcher seeks to locate a target that hides in some unknown position of the environment. Such problems are typically considered to be of an on-line nature, in that the target's position is unknown to the searcher, and the performance of a search strategy is usually analyzed by means of the standard framework of the competitive ratio, which compares the cost incurred by the searcher to an optimal strategy that knows the location of the target. However, one can argue that even for simple search problems, competitive analysis fails to distinguish between strategies which, intuitively, should have different performance in practice. Motivated by the above observation, in this work we introduce and study measures supplementary to competitive analysis in the context of search problems. In particular, we focus on the well-known problem of linear search, informally known as the cow-path problem, for which there is an infinite number of strategies that achieve an optimal competitive ratio equal to 9. We propose a measure that reflects the rate at which the line is being explored by the searcher, and which can be seen as an extension of the bijective ratio over an uncountable set of requests. Using this measure we show that a natural strategy that explores the line aggressively is optimal among all 9-competitive strategies. This provides, in particular, a strict separation from the competitively optimal doubling strategy, which is much more conservative in terms of exploration. We also provide evidence that this aggressiveness is requisite for optimality, by showing that any optimal strategy must mimic the aggressive strategy in its first few explorations. [ABSTRACT FROM AUTHOR]

Groups and communities have been key topics in the information systems (IS) research agenda. While communities are assumed to emerge at the intersection of overlapping groups and their practices, prior research has mainly focused on their dynamics and evolution. This has resulted to limited empirical support regarding the emergence of communities. We address that lacuna by tracing the emergence of communities through the prism of resource mobilization theory. In doing so, we make use of a unique longitudinal dataset and incorporate Topic Modelling, Bipartite Network Analysis, and Community Detection. We show that new communities are formed at the intersection of overlapping groups and practices. In addition, we contribute to the IS literature by demonstrating that their emergence occurs due to resource mobilization that gives rise to a shared mindset. We also reveal that multiple resources are incorporated into the practices of an emerging community. By combining large datasets and innovative computational approaches, we help IS theory and practice to move away from traditional "what" questions towards the more insightful "how" ones. We discuss the theoretical and practical implications of our work and delineate an agenda for future research on the topic. [ABSTRACT FROM AUTHOR]

Competition on e-commerce platforms is becoming increasingly fierce, due to the ease of online searching for comparing products and services. We examine how the sequential browsing behavior of consumers can enable targeted marketing strategies on e-commerce platforms, by using clickstream data from one of the largest e-commerce platforms in Asia. We deploy duration analysis to i) explore how path dependence can better explain consumers' sequential browsing behavior in different product categories, and ii) characterize the sequential browsing behavior of heterogeneous consumer groups. The findings of our work showcase i) the high accuracy of using sequential browsing path dependence to explain consumer behavior, ii) the patterns of their behavioral intentions and iii) the spell of the behavior of heterogeneous consumer groups. Our findings provide nuanced implications for strategically managing branding, marketing, and customer relations on e-commerce platforms. We discuss the implications of our findings for both research and practice, and we delineate an agenda for future research on the topic. [ABSTRACT FROM AUTHOR]

This paper addresses two classes of different, yet interrelated optimization problems. The first class of problems involves a mobile searcher that must locate a hidden target in an environment that consists of a set of unbounded, concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. Both types of problems capture fundamental aspects of resource allocation under uncertainty. We study several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems, we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several well-motivated settings can be addressed using the same underlying approach. [ABSTRACT FROM AUTHOR]

We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter k. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most k such actions per edge take place, where k is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. (Inf Process Lett 113(3):81–86, 2013), whereas the special case k = 2 was studied by Boyar et al. (Proceedings of the 15th workshop on algorithms and data structures (WADS), pp 217–228, 2017). In the first part of this paper we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP of Avitabile et al., by exploiting the structure of the matching problem. In addition, we show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call L-Greedy, and we show that for small values of k it outperforms the algorithm AMP. In terms of lower bounds, we show that no deterministic algorithm better than 1 + 1 / (k - 1) exists, improving upon the known lower bound of 1 + 1 / k . The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of L-Greedy and AMP carry through in this model; moreover we show a lower bound of (k 2 - 3 k + 6) / (k 2 - 4 k + 7) for all even k ≥ 4 . For k ∈ { 2 , 3 } , the competitive ratio is 3/2. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of designing an interruptible system in a setting which involves n problem instances. The system schedules executions of a contract algorithm (which offers a trade-off between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system outputs the currently best solution to each of the n problem instances. The quality of this output is then compared to the best possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all n problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. In this work, we first introduce new measures for evaluating the performance of interruptible systems in this setting. In particular, we propose the deficiency of a schedule as a performance measure that meets the requirements of the problem at hand. We then present a schedule whose performance we prove that is within a small factor from optimal in the general, multiprocessor setting. We also show several lower bounds on the deficiency of schedules on a single processor. More precisely, we prove a general lower bound of (n + 1) / n , an improved lower bound for the two-problem setting ( n = 2 ), and a tight lower bound for the class of round-robin schedules. Our techniques can also yield a simpler, alternative proof of the main result of Bernstein et al. (in: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pp 1211–1217, 2003) concerning the performance of cyclic schedules in multiprocessor environments. [ABSTRACT FROM AUTHOR]

Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. When there is a uniform distribution over the request sequences, this technique reduces to bijective analysis. These methods have been applied in problems such as paging, list update, bin colouring, routing in array mesh networks, and in connection with Bloom filters, and have often provided a clear separation between algorithms whose performance varies significantly in practice. Despite their appealing properties, the above techniques are quite stringent, in that a relation between online algorithms may be either too difficult to establish analytically, or worse, may not even exist. In this paper, we propose remedies to these shortcomings. Our objective is to make all online algorithms amenable to the techniques of stochastic dominance and bijective analysis. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of well-studied online problems such as weighted paging, reordering buffer management, and 2-server on the circle. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This makes it possible to compare two arbitrary online algorithms for an arbitrary online problem. In addition, the bijective ratio is a generalization of the Max/Max ratio (due to Ben-David and Borodin), and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous k-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of O(k) across these metrics. [ABSTRACT FROM AUTHOR]

We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal–dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing ∑ j w j g (F j) , where w j is the job weight, F j is the flow time and g is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which g is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints. [ABSTRACT FROM AUTHOR]

In this paper we study the online variant of two well-known Steiner tree problems. In the online setting, the input consists of a sequence of terminals; upon arrival of a terminal, the online algorithm must irrevocably buy a subset of edges and vertices of the graph so as to guarantee the connectivity of the currently revealed part of the input. More precisely, we first study the online node-weighted Steiner tree problem, in which both edges and vertices are weighted, and the objective is to minimize the total cost of edges and vertices in the solution. We then address the online priority Steiner tree problem, in which each edge and each request are associated with a priority value, which corresponds to their bandwidth support and requirement, respectively. Both problems have applications in the domain of multicast network communications and have been studied from the point of view of approximation algorithms. Motivated by the observation that competitive analysis gives very pessimistic and unsatisfactory results when the only relevant parameter is the number of terminals, we introduce an approach based on parameterized analysis of online algorithms. In particular, we base the analysis on additional parameters that help reveal the true complexity of the underlying problem, and allow a much finer classification of online algorithms based on their performance. More specifically, for the online node-weighted Steiner tree problem, we show a tight bound of Θ(max{min{α,k},log k}) on the competitive ratio, where α is the ratio of the maximum node weight to the minimum node weight and k is the number of terminals. For the online priority Steiner tree problem, we show corresponding tight bounds of Θ (b log k b) , when k > b and Θ(k), when k ≤ b, where b is the number of priority levels and k is the number of terminals. Our main results apply to both deterministic and randomized algorithms, as well as to generalized versions of the problems (i.e., to Steiner forest variants). [ABSTRACT FROM AUTHOR]

We introduce a new technique for the analysis of online algorithms, namely bijective analysis, that is based on pair-wise comparison of the costs incurred by the algorithms. Under this framework, an algorithm A is no worse than an algorithm B if there is a bijection π defined over all request sequences of a given size such that the cost of A on σ is no more than the cost of B on B(π(σ)). We also study a relaxation of bijective analysis, termed average analysis, in which we compare two algorithms based on their corresponding average costs over request sequences of a given size. We apply these new techniques in the context of two fundamental online problems, namely paging and list update. For paging, we show that any two lazy online algorithms are equivalent under bijective analysis. This result demonstrates that, without further assumptions on characteristics of request sequences, it is unlikely, or even undesirable, to separate online paging algorithms based on their performance. However, once we restrict the set of request sequences to those exhibiting locality of reference, and in particular using a model of locality due to Albers et al. (J Comput Syst Sci 70(2):145-175, 2005), we demonstrate that Least-Recently-Used (LRU) is the unique optimal strategy according to average analysis. This is, to our knowledge, the first deterministic model to provide full theoretical backing to the empirical observation that LRU is preferable in practice. Concerning list update, we obtain similar conclusions, in terms of the bijective comparison of any two online algorithms, and in terms of the superiority (albeit not necessarily unique) of the Move-To-Front (MTF) heuristic in the presence of locality of reference. [ABSTRACT FROM AUTHOR]

In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds of online algorithms for this problem. On the positive side, we first provide a relatively simple algorithm that achieves a competitive ratio arbitrarily close to 1.5, using constant-size advice. Our result implies that 16 bits of advice suffice to obtain a competitive ratio better than any online algorithm without advice, thus improving the previously known bound of O(log(n)) bits required to attain this performance. In addition, we introduce a more complex algorithm that still requires only constant-size advice, and has a competitive ratio arbitrarily close to 1.47012. This is the currently best performance of any online bin packing algorithm with sublinear advice. On the negative side, we extend a construction due to Boyar et al. (Algorithmica 74(1), 507-527 2016) so as to show that no online algorithm with sub-linear advice can be 7/6-competitive, improving on the lower bound of 9/8 from Boyar et al. [ABSTRACT FROM AUTHOR]

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time $$w(t)\le c \cdot t$$ , for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w. [ABSTRACT FROM AUTHOR]

We study two optimization problems in a multiprocessor environment in the presence of set-up costs. The first problem involves multiple parallel searchers (e.g., robots) that must locate a target which lies in one of many concurrent rays, and at an unknown position from their common origin. Every time a searcher turns direction, it incurs a turn cost. The objective is to derive a search strategy for locating the target as efficiently as possible. The second problem involves contract algorithms, namely algorithms in which the available computation time is specified prior to their execution. In particular, we seek a schedule of executions of contract algorithms for several different problems in identical parallel processors so as to efficiently simulate an interruptible algorithm, assuming that each execution incurs a given set-up cost. The performance of the search and scheduling strategies are evaluated by means of well-established measures, namely the competitive ratio and the acceleration ratio, respectively. In this paper we provide near-optimal strategies for the above problems, using an approach based on infinite linear-programming formulations. More precisely, we present a search strategy (resp. schedule) which is optimal when the number of rays (resp. problems) is a multiple of the number of searchers (resp. processors). For the general case, we show that the corresponding solutions are very close to optimal. [ABSTRACT FROM AUTHOR]