Malmö University Publications
Change search
Refine search result
1 - 46 of 46
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Alegría, Carlos
    et al.
    Dipartimento di Ingegneria, Università Roma Tre, Italy.
    Anna, Brötzner
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Schmidt, Christiane
    Linköping University.
    Seara, Carlos
    Department of Mathematics, Universidad Politécnica de Catalunya, Spain.
    The Complexity of the Lower Envelope of Collections of Various Geometric Shapes2024In: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, p. 200-206, article id 25Conference paper (Refereed)
    Abstract [en]

    We study the problem of determining the complexity of the lower envelope of a collection of n geometric objects. For collections of rays; unit length line segments; and collections of unit squares to which we apply at most two transformations from translation, rotation, and scaling, we prove a complexity of Θ(n). If all three transformations are applied to unit squares, then we show the complexity becomes Θ(nα(n)), where α(n) is the slowly growing inverse of Ackermann’s function.

  • 2.
    Anna, Brötzner
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Schmidt, Christiane
    Linköping University.
    The k-Transmitter Watchman Route Problem is NP-Hard Even in Histograms and Star-Shaped Polygons2024In: 40th European Workshop on Computational Geometry: Booklet of abstracts, 2024, Vol. 40, p. 381-387, article id 50Conference paper (Refereed)
    Abstract [en]

    A k-transmitter g in a polygon P, with n vertices, k-sees a point pP if the line segment gp intersects P’s boundary at most k times. In the k-Transmitter Watchman Route Problem we aim to minimize the length of a k-transmitter watchman route along which every point in the polygon—or a discrete set of points in the interior of the polygon—is k-seen. We show that the k-Transmitter Watchman Route Problem for a discrete set of points is NP-hard for histograms, uni-monotone polygons, and star-shaped polygons given a fixed starting point. For histograms and uni-monotone polygons it is also NP-hard without a fixed starting point. Moreover, none of these versions can be approximated to within a factor c · log n, for any constant c > 0.

  • 3.
    Nilsson, Bengt J.
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Schmidt, Christiane
    Department of Science and Technology, Linköping University, Norrköping, Sweden.
    k-Transmitter Watchman Routes2023In: WALCOM: Algorithms and Computation: 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings, Springer, 2023, p. 202-213Conference paper (Refereed)
    Abstract [en]

    We consider the watchman route problem for a k-transmitter watchman: standing at point p in a polygon P, the watchman can see �∈� if ��¯ intersects P’s boundary at most k times—q is k-visible to p. Traveling along the k-transmitter watchman route, either all points in P or a discrete set of points �⊂� must be k-visible to the watchman. We aim for minimizing the length of the k-transmitter watchman route.

    We show that even in simple polygons the shortest k-transmitter watchman route problem for a discrete set of points �⊂� is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the k-transmitter watchman route problem for a given starting point and �⊂� with approximation ratio �(log2⁡(|�|⋅�)log⁡log⁡(|�|⋅�)log⁡|�|) (with |�|=�).

  • 4.
    Bagheri, Alireza
    et al.
    Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.
    Anna, Brötzner
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Farivar, Faezeh
    Science and Research Branch, Islamic Azad University, Tehran, Iran.
    Ghasemi, Rahmat
    Science and Research Branch, Islamic Azad University, Tehran, Iran.
    Keshavarz-Kohjerdi, Fatemeh
    Shahed University, Tehran, Iran.
    Krohn, Erik
    University of Wisconsin, Oshkosh, USA.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Schmidt, Christiane
    Linköping University, Campus Norrköping, Sweden.
    Minsum m watchmen’s routes in Stiegl polygons2023In: XX Spanish Meeting on Computational Geometry: Book of Abstracts, 2023, Vol. 20, p. 41-44, article id 21Conference paper (Refereed)
    Abstract [en]

    We present an O(n2 · min{m, n}) time and O(n · min{m, n}) storage algorithm to compute the minsum set of m watchmen routes given their starting points in a Stiegl polygon ― a staircase polygon where the floor solely consists of one horizontal and one vertical edge ― with n vertices.

    Download full text (pdf)
    fulltext
  • 5.
    Ashvinkumar, Vikrant
    et al.
    Univ Sydney, Sydney, NSW, Australia..
    Gudmundsson, Joachim
    Univ Sydney, Sydney, NSW, Australia..
    Levcopoulos, Christos
    Lund Univ, Lund, Sweden..
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    van Renssen, Andre
    Univ Sydney, Sydney, NSW, Australia..
    Local Routing in Sparse and Lightweight Geometric Graphs2022In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 84, p. 1316-1340Article in journal (Refereed)
    Abstract [en]

    Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O (1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937-951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega (n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O (1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O (1)-competitive routing strategy.

    Download full text (pdf)
    fulltext
  • 6.
    Gibson-Lopez, Matt
    et al.
    The University of Texas at San Antonio, San Antonio, TX, United States.
    Krohn, Erik
    University of Wisconsin - Oshkosh, Oshkosh, WI, United States.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Rayford, Matthew
    University of Wisconsin - Oshkosh, Oshkosh, WI, United States.
    Soderman, Sean
    The University of Texas at San Antonio, San Antonio, TX, United States.
    Żyliński, Paweł
    University of Gdańsk, Gdańsk, Poland.
    On Vertex Guarding Staircase Polygons2022In: LATIN 2022: Theoretical Informatics. LATIN 2022 / [ed] Armando Castañeda; Francisco Rodríguez-Henríquez, Springer, 2022, p. 746-760Conference paper (Refereed)
    Abstract [en]

    In this paper, we consider the variant of the art gallery problem where the input polygon is a staircase polygon. Previous works on this problem gave a 2-approximation for point guarding a staircase polygon (where guards can be placed anywhere in the interior of the polygon and we wish to guard the entire polygon). It is still unknown whether this point guarding variant is NP-hard. In this paper we consider the vertex guarding problem, where guards are only allowed to be placed at the vertices of the polygon, and we wish to guard only the vertices of the polygon. We show that this problem is NP-hard, and we give a polynomial-time 2-approximation algorithm. 

  • 7.
    Krohn, Erik
    et al.
    Department of Computer Science, University of Wisconsin, Oshkosh, Oshkosh, WI, USA.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Schmidt, Christiane
    Linköpings universitet, Kommunikations- och transportsystem.
    Opposing Half Guards2022In: 34th Canadian Conference on Computational Geometry, 2022Conference paper (Refereed)
    Abstract [en]

    We study the art gallery problem for opposing halfguards: guards that can either see to their left or to theirright only. We present art gallery theorems, show thatthe problem is NP-hard in monotone polygons, presentapproximation algorithms for spiral and staircase poly-gons, and show that the location of half guards in 2-guardable polygons is not restricted to extensions.

  • 8.
    Nilsson, Bengt J.
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Orden, David
    Physics and Mathematics Department, Universidad Alcalá, Spain.
    Palios, Leonidas
    Department of Computer Science and Engineering, University of Ioannina, Greece.
    Seara, Carlos
    Departament of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain.
    Żyliński, Paweł
    Institute of Informatics, University of Gdańsk, Poland.
    Illuminating the x-Axis by α-Floodlights2021In: 32nd International Symposium on Algorithms and Computation (ISAAC 2021) / [ed] Ahn, Hee-Kap; Sadakane, Kunihiko, 2021Conference paper (Refereed)
    Abstract [en]

    Given a set S of regions with piece-wise linear boundary and a positive angle α < 90°, we consider the problem of computing the locations and orientations of the minimum number of α-floodlights positioned at points in S which suffice to illuminate the entire x-axis. We show that the problem can be solved in O(n log n) time and O(n) space, where n is the number of vertices of the set S.

    Download full text (pdf)
    fulltext
  • 9.
    Nilsson, Bengt J.
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Vujovic, Gordana
    University of Ljubljana, Slovenia.
    Online Two-Dimensional Vector Packing with Advice2021In: Proc. 12th International Conference on Algorithms and Complexity, CIAC'2021 / [ed] Tiziana Calamoneri and Federico Corò, Springer, 2021, Vol. 12701, p. 381-393Conference paper (Refereed)
    Abstract [en]

    We consider the online two-dimensional vector packing problem, showing a lower bound of 11/5 on the competitive ratio of any AnyFit strategy for the problem. We provide a strategy with competitive ratio max{2,6/(1+3tan(𝜋/4−𝛾/2))+𝜖}max{2,6/(1+3tan⁡(π/4−γ/2))+ϵ} and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range [𝜋/4−𝛾/2,𝜋/4+𝛾/2][π/4−γ/2,π/4+γ/2], for 0≤𝛾<𝜋/30≤γ<π/3. In addition, we give a 5/2-competitive strategy also using logarithmic advice for the unrestricted vectors case. These results should be contrasted to the currently best competitive strategy, FirstFit, having competitive ratio 27/10.

    Download full text (pdf)
    fulltext
  • 10.
    Paraschakis, Dimitris
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    FlowRec: Prototyping Session-based Recommender Systemsin Streaming Mode2020In: PAKDD 2020: Advances in Knowledge Discovery and Data Mining, Springer, 2020Conference paper (Refereed)
    Abstract [en]

    Despite the increasing interest towards session-based and streaming recommender systems, there is still a lack of publicly available evaluation frameworks supporting both these paradigms. To address the gap, we propose FlowRec — an extension of the streaming framework Scikit-Multiflow, which opens plentiful possibilities for prototyping recommender systems operating on sessionized data streams, thanks to the underlying collection of incremental learners and support for real-time performance tracking. We describe the extended functionalities of the adapted prequential evaluation protocol, and develop a competitive recommendation algorithm on top of Scikit-Multiflow’s implementation of a Hoeffding Tree. We compare our algorithm to other known baselines for the next-item prediction task across three different domains.

  • 11.
    Nilsson, Bengt J.
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Żyliński, Paweł
    Institute of Informatics, University of Gdańsk, 80-308 Gdańsk, Poland.
    How to Keep an Eye on Small Things2020In: International journal of computational geometry and applications, ISSN 0218-1959, Vol. 30, no 02, p. 97-120Article in journal (Refereed)
    Abstract [en]

    We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having 𝑛n edges. We also prove that in polygons with holes, there is a constant 𝑐>0c>0 such that no polynomial-time algorithm can solve the problem within an approximation factor of 𝑐log𝑛clogn, unless P=NP. For the second problem, we present a (𝑘+ℎ)(k+h)-FPT algorithm for computing a shortest tour that sees 𝑘k specified points in a polygon with ℎh holes. We also present a 𝑘k-FPT approximation algorithm for this problem having approximation factor 2‾√2. In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of 𝑐log𝑛clogn, for some constant 𝑐>0c>0, unless P=NP.

  • 12.
    Paraschakis, Dimitris
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Matchmaking Under Fairness Constraints: A Speed Dating Case Study2020In: Bias and Social Aspects in Search and Recommendation: First International Workshop, BIAS 2020, Lisbon, Portugal, April 14, Proceedings / [ed] Ludovico Boratto; Stefano Faralli; Mirko Marras; Giovanni Stilo, Springer, 2020, p. 43-57Conference paper (Refereed)
    Abstract [en]

    Reported evidence of biased matchmaking calls into question the ethicality of recommendations generated by a machine learning algorithm. In the context of dating services, the failure of an automated matchmaker to respect the user’s expressed sensitive preferences (racial, religious, etc.) may lead to biased decisions perceived by users as unfair. To address the issue, we introduce the notion of preferential fairness, and propose two algorithmic approaches for re-ranking the recommendations under preferential fairness constraints. Our experimental results demonstrate that the state of fairness can be reached with minimal accuracy compromises for both binary and non-binary attributes.

  • 13.
    Paraschakis, Dimitris
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    On preferential fairness of matchmaking: a speed dating case study2020In: Paradigm Shifts in ICT Ethics: Proceedings of the ETHICOMP 2020, Universidad de Rioja , 2020, p. 360-363Conference paper (Refereed)
  • 14.
    Nilsson, Bengt J.
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Orden, David
    Universidad de Alcalà, Spain.
    Palios, Palios
    University of Ioannina, Greece.
    Seara, Carlos
    Universitat Politècnica de Catalunya, Spain.
    Zylinski, Pawel
    University of Gdansk, Poland.
    Shortest Watchman Tours in Simple Polygons Under Rotated Monotone Visibility2020In: Proceedings of the International Computing and Combinatorics Conference, 2020, Springer, 2020, p. 311-323Conference paper (Refereed)
    Abstract [en]

    We present an O(nrG) time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction θ, while θ varies in[0, 180 ◦ ), obtaining the directions for the tour to be the shortest one overall tours, where n is the number of vertices, r is the number of reflex vertices, and G ≤ r is the maximum number of gates of the polygon used at any time in the algorithm.

    Download full text (pdf)
    fulltext
  • 15.
    Brodén, Björn
    et al.
    Apptus Technologies, Trollebergsvägen 5, Lund, 22229, Sweden.
    Hammar, Mikael
    Apptus Technologies, Trollebergsvägen 5, Lund, 22229, Sweden.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Paraschakis, Dimitris
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    A Bandit-Based Ensemble Framework for Exploration/Exploitation of Diverse Recommendation Components: An Experimental Study within E-Commerce2019In: ACM Transactions on Interactive Intelligent Systems, ISSN 2160-6455, E-ISSN 2160-6463, Vol. 10, no 1, p. 4:1-4:32, article id 4Article in journal (Refereed)
    Abstract [en]

    This work presents an extension of Thompson Sampling bandit policy for orchestrating the collection of base recommendation algorithms for e-commerce. We focus on the problem of item-to-item recommendations, for which multiple behavioral and attribute-based predictors are provided to an ensemble learner. In addition, we detail the construction of a personalized predictor based on k-Nearest Neighbors (kNN), with temporal decay capabilities and event weighting. We show how to adapt Thompson Sampling to realistic situations when neither action availability nor reward stationarity is guaranteed. Furthermore, we investigate the effects of priming the sampler with pre-set parameters of reward probability distributions by utilizing the product catalog and/or event history, when such information is available. We report our experimental results based on the analysis of three real-world e-commerce datasets.

  • 16.
    Gibson, Matt
    et al.
    University of Texas at San Antonio, TX, USA.
    Krohn, Erik
    University of Wisconsin at Oshkosh, WI, USA.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Mathew, Rayford
    University of Wisconsin at Oshkosh, WI, USA.
    Zylinski, Pawel
    University of Gdansk, Poland.
    A Note on Guarding Staircase Polygons2019In: CCCG 2019: Proceedings of the 31st Canadian Conference in Computational Geometry, 2019, p. 105-109Conference paper (Refereed)
    Abstract [en]

    We exhibit two linear time approximation algorithms for guarding rectilinear staircase polygons both having approximation factor 2. The first algorithm benefits from its simplicity, whereas the second provides more insight to the problem.

    Download full text (pdf)
    fulltext
  • 17.
    Ashvinkumar, Vikrant
    et al.
    University of Sydney, Australia.
    Gudmundsson, Joachim
    University of Sydney, Australia.
    Levcopoulos, Christos
    Lund University, Sweden.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    van Renssen, André
    University of Sydney, Australia.
    Local Routing in Sparse and Lightweight Geometric Graphs2019In: LIPICS, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik , 2019Conference paper (Refereed)
    Abstract [en]

    Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.

    Download full text (pdf)
    fulltext
  • 18.
    Chrobak, Marek
    et al.
    Department of Computer Science and Engineering, University of California at Riverside, Riverside, USA.
    Dürr, Christoph
    Laboratoire d’informatique de Paris 6, LIP6, CNRS, Sorbonne Université, 75252, Paris, France.
    Fabijan, Aleksander
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Online Clique Clustering2019In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 82, no 4, p. 938-965Article in journal (Refereed)
    Abstract [en]

    Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online algorithm based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and a strict competitive ratio at most 22.641. We also show that no deterministic algorithm can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is n−ω(1), where n is the number of vertices in the graph.

    Download full text (pdf)
    fulltext
  • 19.
    Nilsson, Bengt J.
    et al.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Zylinski, Pawel
    University of Gdansk, Poland.
    The lighthouse problem navigating by lighthouses in geometric domains2019In: CCCG 2019: Proceedings of the 31st Canadian Conference in Computational Geometry, 2019, p. 71-77Conference paper (Refereed)
    Abstract [en]

    We study the computational properties of placing a minimum number of lighthouses in different geometric domains and under different notions of visibility, enabling a vehicle placed anywhere in the domain to navigate to a given specific target. This problem shares common elements with the art gallery problem in that the whole domain must be covered with as few lighthouses as possible. Our main result is an algorithm that places a minimum set of strip lighthouses in a simple rectilinear polygon. These correspond to sliding cameras in art gallery vernacular. 

  • 20.
    Brodén, Björn
    et al.
    Apptus Technologies, Lund, Sweden.
    Hammar, Mikael
    Apptus Technologies, Lund, Sweden.
    Nilsson, Bengt J.
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Paraschakis, Dimitris
    Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Ensemble Recommendations via Thompson Sampling: an Experimental Study within e-Commerce2018In: Proceeding IUI '18 23rd International Conference on Intelligent User Interfaces, ACM Digital Library, 2018, p. 19-29Conference paper (Refereed)
    Abstract [en]

    This work presents an extension of Thompson Sampling bandit policy for orchestrating the collection of base recommendation algorithms for e-commerce. We focus on the problem of item-to-item recommendations, for which multiple behavioral and attribute-based predictors are provided to an ensemble learner. We show how to adapt Thompson Sampling to realistic situations when neither action availability nor reward stationarity is guaranteed. Furthermore, we investigate the effects of priming the sampler with pre-set parameters of reward probability distributions by utilizing the product catalog and/or event history, when such information is available. We report our experimental results based on the analysis of three real-world e-commerce datasets.

    Download full text (pdf)
    FULLTEXT01
  • 21.
    Brodén, Björn
    et al.
    Apptus Technol, Trollebergsvagen 5, SE-22229 Lund, Sweden.
    Hammar, Mikael
    Apptus Technol, Trollebergsvagen 5, SE-22229 Lund, Sweden.
    Nilsson, Bengt J.
    Malmö högskola, Faculty of Technology and Society (TS).
    Paraschakis, Dimitris
    Malmö högskola, Faculty of Technology and Society (TS).
    Bandit Algorithms for e-Commerce Recommender Systems Extended Abstract2017In: Proceedings of the Eleventh ACM Conference On Recommender Systems (Recsys'17), ACM Digital Library, 2017, p. 349-349Conference paper (Refereed)
    Abstract [en]

    We study bandit algorithms for e-commerce recommender systems. The question we pose is whether it is necessary to consider reinforcement learning effects in recommender systems. A key reason to introduce a recommender system for a product page on an e-commerce site is to increase the order value by improving the chance of making an upsale. If the recommender system merely predicts the next purchase, there might be no positive effect at all on the order value, since the recommender system predicts sales that would have happened independent of the recommender system. What we really are looking for are the false negatives, i.e., purchases that happen as a consequence of the recommender system. These purchases entail the entire uplift and should be present as reinforcement learning effects. This effect cannot be displayed in a simulation of the site, since there are no reinforcement learning effects present in a simulation. The attribution model must capture the uplift to guarantee an increased order value. However, such an attribution model is not practical, due to data sparsity. Given this starting point, we study some standard attribution models for e-commerce recommender systems, and describe how these fare when applied in a reinforcement learning algorithm, both in a simulation and on live sites.

  • 22.
    Langetepe, Elmar
    et al.
    Institute of Computer Science I, University of Bonn, Bonn, 53117, Germany.
    Nilsson, Bengt J.
    Malmö högskola, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).
    Packer, Eli
    Intel Corporation, Givataim, Israel.
    Discrete Surveillance Tours in Polygonal Domains2017Conference paper (Refereed)
    Abstract [en]

    The watchman route of a polygon is a closed tour that sees all points of the polygon. Computing the shortest such tour is a well-studied problem. Another reasonable optimization criterion is to require that the tour mini- mizes the hiding time of the points in the polygon, i.e., the maximum time during which any points is not seen by the agent following the tour at unit speed. We call such tours surveillance routes. We show a linear time 3/2-approximation algorithm for the optimum surveillance tour problem in rectilin- ear polygons using the L_1 -metric. We also present a polynomial time O(polylog w_max )-approximation algo- rithm for the optimum weighted discrete surveillance route in a simple polygon with weight values in the range [1, w_max].

    Download full text (pdf)
    FULLTEXT01
  • 23.
    Nilsson, Bengt J.
    et al.
    Malmö högskola, Faculty of Technology and Society (TS).
    Packer, Eli
    Weighted Discrete Surveillance Tours in Simple Polygons2017In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), 2017Conference paper (Other academic)
    Abstract [en]

    The watchman route problem is a well investigated problem in which a closed tour inside a polygon that satisfies visibility constraints is optimized. We ex- plore a new variant in which a tour needs to see a set of locations inside a polygon so that the maximum time interval in which those locations are not guarded (the delay) is minimized. We call such tours surveil- lance tours. We show that an algorithm that follows the ideas of the classic watchman problem provides a 2-approximation to our problem. We then investi- gate the case where each location is associated with a weight that represents the importance of not leaving the location unguarded for long periods. Thus, the tour is required to see locations with larger weights more frequently. We show that this variant is NP- hard and present two approximation algorithms.

    Download full text (pdf)
    FULLTEXT01
  • 24.
    Nilsson, Bengt J.
    et al.
    Malmö högskola, Faculty of Technology and Society (TS), Department of Computer Science (DV).
    Packer, Eli
    An Approximation Algorithm for the Two-Watchman Route in a Simple Polygon2016In: EuroCG 2016: 32nd European Workshop on Computational Geometry March 30 – April 1, 2016 Book of Abstracts / [ed] Evanthia Papadopoulou, 2016, p. 111-114Conference paper (Other academic)
    Abstract [en]

    The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has minimal length, and the minsum measure, where we want the tours for which the sum of their lengths is smallest. It is known that computing the minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. We exhibit a polynomial time 7.1416-factor approximation algorithm for computing the minmax two-watchman route in simple polygons.

    Download full text (pdf)
    FULLTEXT01
  • 25.
    Paraschakis, Dimitris
    et al.
    Malmö högskola, Faculty of Technology and Society (TS).
    Nilsson, Bengt
    Malmö högskola, Faculty of Technology and Society (TS).
    Holländer, John
    Comparative Evaluation of Top-N Recommenders in e-Commerce: an Industrial Perspective2015In: Proceedings: 2015 IEEE 14th International Conference on Machine Learning and Applications, ICMLA 2015, IEEE, 2015, p. 1024-1031Conference paper (Refereed)
    Abstract [en]

    We experiment on two real e-commerce datasets and survey more than 30 popular e-commerce platforms to reveal what methods work best for product recommendations in industrial settings. Despite recent academic advances in the field, we observe that simple methods such as best-seller lists dominate deployed recommendation engines in e-commerce. We find our empirical findings to be well-aligned with those of the survey, where in both cases simple personalized recommenders achieve higher ranking than more advanced techniques. We also compare the traditional random evaluation protocol to our proposed chronological sampling method, which can be used for determining the optimal time-span of the training history for optimizing the performance of algorithms. This performance is also affected by a proper hyperparameter tuning, for which we propose golden section search as a fast alternative to other optimization techniques.

    Download full text (pdf)
    FULLTEXT01
  • 26. Chrobak, Marek
    et al.
    Dürr, Christoph
    Nilsson, Bengt J.
    Malmö högskola, Faculty of Technology and Society (TS).
    Competitive Strategies for Online Clique Clustering2015In: Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015: Proceedings, Springer, 2015, p. 101-113Conference paper (Refereed)
    Abstract [en]

    A clique clustering of a graph is a partitioning of its vertices into disjoint cliques. The quality of a clique clustering is measured by the total number of edges in its cliques. We consider the online variant of the clique clustering problem, where the vertices of the input graph arrive one at a time. At each step, the newly arrived vertex forms a singleton clique, and the algorithm can merge any existing cliques in its partitioning into larger cliques, but splitting cliques is not allowed. We give an online strategy with competitive ratio 15.645 and we prove a lower bound of 6 on the competitive ratio, improving the previous respective bounds of 31 and 2.

    Download full text (pdf)
    FULLTEXT01
  • 27.
    Levcopoulos, Christos
    et al.
    Lund University.
    Lingas, Andrzej
    Lund University.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Zylinski, Pawel
    University of Gdańsk, Poland.
    Clearing Connections by Few Agents2014In: Fun with algorithms, 2014, p. 289-300Conference paper (Refereed)
    Abstract [en]

    We study the problem of clearing connections by agents placed at some vertices in a directed graph. The agents can move only along directed paths. The objective is to minimize the number of agents guaranteeing that any pair of vertices can be connected by a underlying undirected path that can be cleared by the agents. We provide several results on the hardness, approximability and parameterized complexity of the problem. In particular, we show it to be: NP-hard, 2-approximable in polynomial-time, and solvable exactly in O(alpha n^3 2^{2alpha}) time, where alpha is the number of agents in the solution. In addition, we give a simple linear-time algorithm optimally solving the problem in digraphs whose underlying graphs are trees. Finally, we discuss a related problem, where the task is to clear with a minimum number of agents a subgraph of the underlying graph containing its spanning tree. We show that this problem also admits a 2-approximation in polynomial time.

    Download full text (pdf)
    FULLTEXT01
  • 28.
    Nilsson, Bengt J.
    et al.
    Malmö högskola, School of Technology (TS).
    Zylinski, Pawel
    How to Keep an Eye on a Few Small Things2014Conference paper (Refereed)
    Abstract [en]

    We present a (k +h)-FPT algorithm for computing a shortest tour that sees k specified points in a polygon with h holes. We also present a k-FPT approximation algorithm for this problem having approximation factor √2. In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of (log n), unless P=NP, where n is the total number of edges of the polygon.

    Download full text (pdf)
    FULLTEXT01
  • 29. Krohn, Erik A.
    et al.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Approximate Guarding of Monotone and Rectilinear Polygons2013In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 66, no 3, p. 564-594Article in journal (Refereed)
    Abstract [en]

    We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is \OPT\ for a rectilinear polygon, our algorithm produces a guard set of size~$O(\OPT^2)$.

    Download full text (pdf)
    FULLTEXT01
  • 30.
    Fabijan, Aleksander
    et al.
    Malmö högskola, School of Technology (TS).
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Persson, Mia
    Malmö högskola, School of Technology (TS).
    Competitive Online Clique Clustering2013In: Proceedings of the 8th International Conference on Algorithms and Complexity;8, Springer, 2013, p. 221-233Conference paper (Refereed)
    Abstract [en]

    Clique clustering is the problem of partitioning a graph into cliques so that some objective function is optimized. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The objective here is to maintain a clustering the never deviates too far in the objective function compared to the optimal solution. We give a constant competitive upper bound for online clique clustering, where the objective function is to maximize the number of edges inside the clusters. We also give almost matching upper and lower bounds on the competitive ratio for online clique clustering, where we want to minimize the number of edges between clusters. In addition, we prove that the greedy method only gives linear competitive ratio for these problems.

    Download full text (pdf)
    FULLTEXT01
  • 31.
    Hammar, Mikael
    et al.
    Apptus Technologies, Lund, Sweden.
    Karlsson, Robin
    Apptus Technologies, Lund, Sweden.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Using Maximum Coverage to Optimize Recommendation Systems in E-Commerce2013In: Proceedings of the 7th ACM conference on Recommender systems, ACM Digital Library, 2013, p. 265-272Conference paper (Other academic)
    Abstract [en]

    We study the problem of optimizing recommendation systems for e-commerce sites. We consider in particular a combinatorial solution to this optimization based on the well known Maximum Coverage problem that asks for the k sets (products) that cover the most elements from a ground set (consumers). This formulation provides an abstract model for what k products should be recommended to maximize the probability of consumer purchase. Unfortunately, Maximum Coverage is NP-complete but an efficient approximation algorithm exists based on the Greedy methodology.We exhibit test results from the Greedy method on real data sets showing 3-8% increase in sales using the Maximum Coverage optimization method in comparison to the standard best-seller list. A secondary effect that our Greedy algorithm exhibits on the tested data is increased diversification in presented products over the best-seller list.

    Download full text (pdf)
    FULLTEXT01
  • 32.
    Krohn, Erik
    et al.
    Department of Computer Science, University of WisconsinOshkosh, Oshkosh, WI, USA.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    The Complexity of Guarding Monotone Polygons2012In: 24th Canadian Conference on Computational Geometry, August 8-10, 2012 Charlottetown, Canada, 2012, p. 167-172Conference paper (Refereed)
    Abstract [en]

    A polygon P is x-monotone if any line orthogonal to the x-axis has a simply connected intersection with P. A set G of points inside P or on the boundary of P is said to guard the polygon if every point inside P or on the boundary of P is seen by a point in G. An interior guard can lie anywhere inside or on the boundary of the polygon. Using a reduction from Monotone 3SAT, we prove that the decision version of this problem is NP-hard. Because interior guards can be placed anywhere inside the polygon, a clever gadget is introduced that forces interior guards to be placed at very specific locations.

    Download full text (pdf)
    FULLTEXT01
  • 33.
    Amhag, Lisbeth
    et al.
    Malmö högskola, School of Technology (TS). Malmö högskola, School of Teacher Education (LUT), School Development and Leadership (SOL).
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS). Malmö högskola, School of Teacher Education (LUT), School Development and Leadership (SOL).
    e-Läranderesurser i Sverige2010In: Från didaktik till e-didaktik, Malmö högskola, 2010, p. 397-410Chapter in book (Other academic)
    Abstract [en]

    We give a brief history of distance learning in Sweden. We then present the main electronically available resources that have been established in recent years for learning purposes. We divide the resources into two categories: Administrative resources. These include LMS-systems and other systems to administer applications, student result, course material, etc. We present studera.nu which is the Swedish application website for all university courses and programs, Ladok and Skola24, the student result databases for universities and schools, nationwide. Educational resources. These are mainly web-based systems containing material that can be used for education. We present LIBRIS Uppsök and SwePub, the two Swedish National Libary websites containing all theses and essays published at Swedish universities. We also look at the electronic library search system for Malmö University as an example of an online library system. Finally, we discuss internationally available resources such as Wikipedia, Google search and Google scholar as well as the educational aspects of social networking systems such as Facebook, Myspace and Classroom 2.0.

    Download full text (pdf)
    FULLTEXT01
  • 34.
    Nilsson, Bengt J.
    et al.
    Malmö högskola, School of Technology (TS).
    Niubo, John
    Erfarenheter av e-lärande i Sverige - en fallstudie2010In: Från didaktik till e-didaktik: paradigmer, modeller och tekniker för e-lärande, Malmö högskola, 2010, p. 389-395Chapter in book (Other academic)
    Abstract [en]

    We present a university course in "Web Development" that has been taught at Malmö University since 2002 as a distance and e-learning course. We discuss course content, objectives and student results as a function of web-based course material and e-learning set-up. We study the positive and negative effects of "availability." Many of the solutions and methods taught in the course are available on the web. How does this affect learning and how does one move from copying as a way of cheaingt, to copying as a means of learning? Over time the outside parameters of the course have changed, e.g., the "Learning Management Systems" (LMS) have changed three times since the conception of the course. We present a short list of requirements for LMS-systems to be able to function well in e-learning courses in higher education.

    Download full text (pdf)
    FULLTEXT01
  • 35. D'Angelo, Giuseppe
    et al.
    Nilsson, Bengt J.
    Från didaktik till e-didaktik: paradigmer, modeller och tekniker för e-lärande2010Collection (editor) (Other academic)
    Download full text (pdf)
    FULLTEXT01
  • 36.
    Hammar, Mikael
    et al.
    Department of Computer Science, Salerno University, Baronissi (SA) 84081, Italy.
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Persson, Mia
    Malmö högskola, School of Technology (TS).
    Competitive Exploration of Rectilinear Polygons2006In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 354, no 3, p. 367-378Article in journal (Refereed)
    Abstract [en]

    Exploring a polygon with robots, when the robots do not have knowledge of the surroundings can be viewed as an online problem. Typical for online problems is that decisions must be made based on past events without complete information about the future. In our case the robots do not have complete information about the environment. Competitive analysis can be used to measure the performance of methods solving online problems. The competitive ratio of such a method is the ratio between the method's performance and the performance of the best method having full knowledge of the future. We are interested in obtaining good bounds on the competitive ratio of exploring polygons and prove constant competitive strategies and lower bounds for exploring a simple rectilinear polygon in the $L_1$ metric.

    Download full text (pdf)
    FULLTEXT01
  • 37.
    Hammar, Mikael
    et al.
    Apptus Technologies AB, IDEON, SE-223 70, Lund, Sweden.
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Persson, Mia
    Malmö högskola, School of Technology (TS).
    The Online Freeze-Tag Problem2006In: LATIN 2006: Theoretical Informatics, Springer, 2006, p. 569-579Conference paper (Refereed)
    Abstract [en]

    We consider the following problem from swarm robotics:given one or more “awake” robots in some metric space M, wake upa set of “asleep” robots. A robot awakens a sleeping robot by moving tothe sleeping robot’s position. When a robot awakens, it is available toassist in awakening other slumbering robots. We investigate offline andonline versions of this problem and give a 2-competitive strategy and alower bound of 2 in the case when M is discrete and the objective isto minimize the total movement cost. We also study the case when Mis continuous and show a lower bound of 7/3 when the objective is tominimize the time when the last robot awakens.

    Download full text (pdf)
    FULLTEXT01
  • 38.
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Approximate Guarding of Monotone and Rectilinear Polygons2005In: Automata, Languages and Programming, Springer, 2005, p. 1362-1373Conference paper (Refereed)
    Abstract [en]

    We show a constant factor approximation algorithm for interior guarding of monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT 2).

    Download full text (pdf)
    FULLTEXT01
  • 39. Brodén, Björn
    et al.
    Hammar, Mikael
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Online and Offline Algorithms for the Time-Dependent TSP with Time Zones2004In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 39, no 4, p. 299-319Article in journal (Refereed)
    Abstract [en]

    The time dependent traveling salesman problem is a variant of TSP with time dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of \tdtsp. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.

    Download full text (pdf)
    FULLTEXT01
  • 40. Hammar, Mikael
    et al.
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Approximation Results for Kinetic Variants of TSP2002In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 27, no 4, p. 635-651Article in journal (Refereed)
    Abstract [en]

    We study the approximation complexity of certain kinetic variants of the Traveling Salesman Problem where we consider instances where points move with fixed constant velocity in a fixed direction. We prove the following results: 1. If the points all move with the same velocity and in the same direction, then there is a PTAS for the Kinetic TSP. 2. The Kinetic TSP cannot be approximated better than by a factor of two by a polynomial time algorithm unless P=NP, even if there are only two moving points in the instance. \item The Kinetic TSP cannot be approximated better than by a factor of $2^{\Omega(\sqrt{n})}$ by a polynomial time algorithm unless P=NP, where $n$ is the size of the input instance, even if the maximum velocity is bounded.

    Download full text (pdf)
    FULLTEXT01
  • 41. Hammar, Mikael
    et al.
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Schuierer, Sven
    Improved Exploration of Rectilinear Polygons2002In: Nordic Journal of Computing, ISSN 1236-6064, Vol. 9, no 1, p. 32-53Article in journal (Refereed)
    Abstract [en]

    We prove a 5/3-competitive strategy for exploring a simple rectilinear polygon in the $L_1$ metric. This improves the previous factor two bound of Deng, Kameda and Papadimitriou.

    Download full text (pdf)
    FULLTEXT01
  • 42.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Approximating a Shortest Watchman Route2001In: Fundamenta Informaticae, Vol. 45, no 3, p. 253-281Article in journal (Refereed)
    Abstract [en]

    We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in $O(n\log n)$ time as compared to the best known algorithm that computes a shortest watchman route which runs in $O(n^6)$ time.

  • 43. Brodén, Björn
    et al.
    Hammar, Mikael
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Guarding Lines and 2-Link Polygons is APX-hard2001Conference paper (Other academic)
    Abstract [en]

    We prove that the minimum line covering problem and the minimum guard covering problem restricted to 2-link polygons are APX-hard.

    Download full text (pdf)
    FULLTEXT01
  • 44. Eliasson, Bo
    et al.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    New Technology for Safe Critical Applications in Real Time2001Conference paper (Other academic)
    Abstract [en]

    Several techniques are available for constraint satisfaction problems. Most of them lack real time capability and distributed computational properties. Configuration of complex systems has today become a competitive edge, e.g. within e-business. The other side of the same coin can be used for diagnosis and simulation of safe critical applications. This paper gives a scientific background and comparison of methods for constraint satisfaction problems implemented in real time environment. Especially, the technique and its features of the array-based logic will be illustrated by three examples. The examples are: 1.Modelling and simulation of system wide protection applications of power systems 2.Modelling, simulation and implementation of safe critical switching in power systems 3.Modelling, simulation and implementation of safe critical systems of automatic train control Array-based logic is a novel technology, which is founded on a geometrical representation of logic in terms of nested data arrays. In this representation, logical inferences are executed on finite domain systems by a few standardised array operations. In computational practice, array-based logic makes it possible to solve large-scale constraint problems with combinations very efficiently. The major advantages of the technology are completeness, compactness, and speed of simulation (real-time capability), all of which derive from intrinsic properties of the underlying geometrical model. A system in array-based logic is considered analogously to electrical networks and is thus described by the constraints of the isolated elements as well as the constraints of the interconnected elements (the system topology). All system constraints are eliminated in accordance with the methods known from electrical network theory and other engineering disciplines rooted in classical physics. The configuration space is represented explicitly in terms of nested data arrays and the system can therefore be simulated in real-time by co-ordinate indexing on these arrays. This data driven approach makes it suitable for parallel processing, which is an important quality for distributed systems.

    Download full text (pdf)
    FULLTEXT01
  • 45.
    Hammar, Mikael
    et al.
    Department of Computer Science, Lund University, Box 118, S-221 00 Lund, Sweden.
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Schuierer, Sven
    Institut für Informatik, Georges-Köhler-Allee, Geb. 051, D-79110 Freiburg, Germany.
    Parallel Searching on m Rays2001In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 18, no 3, p. 125-139Article in journal (Refereed)
    Abstract [en]

    We investigate parallel searching on $m$ concurrent rays. We assume that a target $t$ is located somewhere on one of the rays; we are given a group of $m$ point robots each of which has to reach $t$. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy $S$ we are interested in the competitive ratio defined as the ratio of the time needed by the robots to reach $t$ using $S$ and the time needed to reach $t$ if the location of $t$ is known in advance. If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of~9 --- independent of $m$. We show that 9 is a lower bound on the competitive ratio for two large classes of strategies if $m\geq 2$. If the minimum distance to the target is not known in advance, we show a lower bound on the competitive ratio of $1 + 2 (k + 1)^{k + 1} / k^k$ where $k = \left\lceil\log m\right\rceil$ where $\log$ is used to denote the base 2 logarithm. We also give a strategy that obtains this ratio.

    Download full text (pdf)
    FULLTEXT01
  • 46. Krznaric, Drago
    et al.
    Levcopoulos, Christos
    Nilsson, Bengt J.
    Malmö högskola, School of Technology (TS).
    Minimum Spanning Trees in d Dimensions1999In: Nordic Journal of Computing, Vol. 6, no 4, p. 446-461Article in journal (Refereed)
    Abstract [en]

    It is shown that a minimum spanning tree of $n$ points in $R^d$ under any fixed $L_p$-metric, with $p=1,2,\ldots,\infty$, can be computed in optimal $O(T_d(n,n) )$ time in the algebraic computational tree model. $T_d(n,m)$ denotes the time to find a bichromatic closest pair between $n$ red points and $m$ blue points. The previous bound in the model was $O( T_d(n,n) \log n )$ and it was proved only for the $L_2$ (Euclidean) metric. Furthermore, for $d = 3$ it is shown that a minimum spanning tree can be found in $O(n \log n)$ time under the $L_1$ and $L_\infty$-metrics. This is optimal in the algebraic computation tree model. The previous bound was $O(n \log n \log \log n)$.

1 - 46 of 46
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf