Search

Your search keyword '"Moehring, Rolf H."' showing total 273 results
Start Over Author "Moehring, Rolf H."

Refine your results

more »

more »

273 results on '"Moehring, Rolf H."'

2. Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

Author

Wang, Yishui, Möhring, Rolf H., Wu, Chenchen, Xu, Dachuan, and Zhang, Dongmei

Subjects
Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, 68W25, 90B10, 90B80, F.2.2, G.2.1
Abstract

In this paper, we consider two types of robust models of the $k$-median/$k$-means problems: the outlier-version ($k$-MedO/$k$-MeaO) and the penalty-version ($k$-MedP/$k$-MeaP), in which we can mark some points as outliers and discard them. In $k$-MedO/$k$-MeaO, the number of outliers is bounded by a given integer. In $k$-MedP/$k$-MeaP, we do not bound the number of outliers, but each outlier will incur a penalty cost. We develop a new technique to analyze the approximation ratio of local search algorithms for these two problems by introducing an adapted cluster that can capture useful information about outliers in the local and the global optimal solution. For $k$-MeaP, we improve the best known approximation ratio based on local search from $25+\varepsilon$ to $9+\varepsilon$. For $k$-MedP, we obtain the best known approximation ratio. For $k$-MedO/$k$-MeaO, there exists only two bi-criteria approximation algorithms based on local search. One violates the outlier constraint (the constraint on the number of outliers), while the other violates the cardinality constraint (the constraint on the number of clusters). We consider the former algorithm and improve its approximation ratios from $17+\varepsilon$ to $3+\varepsilon$ for $k$-MedO, and from $274+\varepsilon$ to $9+\varepsilon$ for $k$-MeaO.

Published
2020

3. A convergence analysis of the price of anarchy in atomic congestion games

Author

Wu, Zijun, Moehring, Rolf H., Ren, Chunying, and Xu, Dachuan

Subjects
Computer Science - Computer Science and Game Theory, Economics - Theoretical Economics
Abstract

This paper provides a comprehensive convergence analysis of the PoA of both pure and mixed Nash equilibria in atomic congestion games with unsplittable demands., Comment: 57 pages

Published
2020
Full Text
View/download PDF

4. A constant FPT approximation algorithm for hard-capacitated k-means

Author

Xu, Yicheng, Möhring, Rolf H., Xu, Dachuan, Zhang, Yong, and Zou, Yifei

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics
Abstract

Hard-capacitated $k$-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and data mining areas. In this problem, one is required to partition a given $n$-point set into $k$ disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard and for which most of the work is from a meta heuristic perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT($k$) algorithm with performance guarantee of $69+\epsilon$ for any HCKM instances in this paper.

Published
2019

5. Selfishness need not be bad: a general proof

Author

Wu, Zijun, Möhring, Rolf H., and Xu, Dachuan

Subjects
Computer Science - Computer Science and Game Theory
Abstract

This article studies the user behavior in non-atomic congestion games. We consider non-atomic congestion games with continuous and non-decreasing functions and investigate the limit of the price of anarchy when the total user volume approaches infinity. We deepen the knowledge on {\em asymptotically well designed games} \cite{Wu2017Selfishness}, {\em limit games} \cite{Wu2017Selfishness}, {\em scalability} \cite{Wu2017Selfishness} and {\em gaugeability} \cite{Colini2017b} that were recently used in the limit analyses of the price of anarchy for non-atomic congestion games. We develop a unified framework and derive new techniques that allow a general limit analysis of the price of anarchy. With these new techniques, we are able to prove a global convergence on the price of anarchy for non-atomic congestion games with arbitrary polynomial price functions and arbitrary user volume vector sequences. Moreover, we show that these new techniques are very flexible and robust and apply also to non-atomic congestion games with price functions of other types. In particular, we prove that non-atomic congestion games with regularly varying price functions are also asymptotically well designed, provided that the price functions are slightly restricted. Our results greatly generalize recent results. In particular, our results further support the view with a general proof that selfishness need not be bad for non-atomic congestion games., Comment: 68 pages, 2 figures

Published
2018

7. Strong Nash Equilibria in Games with the Lexicographical Improvement Property

Author

Harks, Tobias, Klimm, Max, and Moehring, Rolf H.

Subjects
Computer Science - Computer Science and Game Theory, Computer Science - Discrete Mathematics
Abstract

We introduce a class of finite strategic games with the property that every deviation of a coalition of players that is profitable to each of its members strictly decreases the lexicographical order of a certain function defined on the set of strategy profiles. We call this property the Lexicographical Improvement Property (LIP) and show that it implies the existence of a generalized strong ordinal potential function. We use this characterization to derive existence, efficiency and fairness properties of strong Nash equilibria. We then study a class of games that generalizes congestion games with bottleneck objectives that we call bottleneck congestion games. We show that these games possess the LIP and thus the above mentioned properties. For bottleneck congestion games in networks, we identify cases in which the potential function associated with the LIP leads to polynomial time algorithms computing a strong Nash equilibrium. Finally, we investigate the LIP for infinite games. We show that the LIP does not imply the existence of a generalized strong ordinal potential, thus, the existence of SNE does not follow. Assuming that the function associated with the LIP is continuous, however, we prove existence of SNE. As a consequence, we prove that bottleneck congestion games with infinite strategy spaces and continuous cost functions possess a strong Nash equilibrium.

Published
2009

10. Proper and Unit Trapezoid Orders and Graphs

Author

Bogart, Kenneth P., Möhring, Rolf H., and Ryan, Stephen P.

Subjects
Mathematics - Combinatorics
Abstract

We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval orders, where the class of proper interval orders is exactly the same as the class of unit interval orders.

Published
1996

11. Area Editors' Statements

Author

Bhargava, Hemant K., Dyer, James S., Hobbs, Benjamin F., Bertsimas, Dimitris, van Ryzin, Garrett J., Washburn, Alan R., Möhring, Rolf H., Harris, Carl M., Kaplan, Edward H., Fu, Michael C., Yao, David D., Cooper, Robert B., and Toth, Paolo

Published
2000

12. Integrating Sequencing and Scheduling: A Generic Approach with Two Exemplary Industrial Applications

Author

Höhn, Wiebke, Möhring, Rolf H., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kliemann, Lasse, editor, and Sanders, Peter, editor

Published
2016
Full Text
View/download PDF

15. A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling

Author

Berthold, Timo, Heinz, Stefan, Lübbecke, Marco E., Möhring, Rolf H., Schulz, Jens, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Lodi, Andrea, editor, Milano, Michela, editor, and Toth, Paolo, editor

Published
2010
Full Text
View/download PDF

17. Characterizing the Existence of Potential Functions in Weighted Congestion Games

Author

Harks, Tobias, Klimm, Max, Möhring, Rolf H., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Mavronicolas, Marios, editor, and Papadopoulou, Vicky G., editor

Published
2009
Full Text
View/download PDF

18. Traffic Networks and Flows over Time

Author

Köhler, Ekkehard, Möhring, Rolf H., Skutella, Martin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Lerner, Jürgen, editor, Wagner, Dorothea, editor, and Zweig, Katharina A., editor

Published
2009
Full Text
View/download PDF

23. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables — and Beyond

Author

Liebchen, Christian, Möhring, Rolf H., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Geraets, Frank, editor, Kroon, Leo, editor, Schoebel, Anita, editor, Wagner, Dorothea, editor, and Zaroliagis, Christos D., editor

Published
2007
Full Text
View/download PDF

26. Partitioning Graphs to Speed Up Dijkstra’s Algorithm

Author

Möhring, Rolf H., Schilling, Heiko, Schütz, Birk, Wagner, Dorothea, Willhalm, Thomas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Nikoletseas, Sotiris E., editor

Published
2005
Full Text
View/download PDF

27. Acceleration of Shortest Path and Constrained Shortest Path Computation

Author

Köhler, Ekkehard, Möhring, Rolf H., Schilling, Heiko, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Nikoletseas, Sotiris E., editor

Published
2005
Full Text
View/download PDF

42. The pathwidth and treewidth of cographs

Author

Bodlaender, Hans L., Möhring, Rolf H., Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Gilbert, John R., editor, and Karlsson, Rolf, editor

Published
1990
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results