BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Bodo Manthey

Bodo Manthey contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithmsmath.PR

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2022arXiv

Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP

We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Hajek explores members of the solution set which are in expectation far from the global optimum. We obtain a lower bound on the expected length of the final tour obtained by SA on these random instances. In addition, we also obtain an upper bound on the expected value of its variance. These bounds assume that the Markov chain that describes SA is stationary, a situation that does not truly hold in practice. Hence, we also formulate conditions under which the bounds extend to the nonstationary case. These bounds are obtained by comparing the tour length distribution to a related distribution. We furthermore provide numerical evidence for a stochastic dominance relation that appears to exist between these two distributions, and formulate a conjecture in this direction. If proved, this conjecture implies that SA stays far from the global optimum with high probability when executed for any sub-exponential number of iterations. This would show that SA requires at least exponentially many iterations to reach a global optimum with nonvanishing probability.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics

Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by Bringmann et al. (Algorithmica, 2013), who have used random shortest path metrics on complete graphs to analyze heuristics. The goal of this paper is to generalize these findings to non-complete graphs, especially Erdős-Rényi random graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances, we prove that the greedy heuristic for the minimum distance maximum matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the $k$-median problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2-opt heuristic for the traveling salesman problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximability of Connected Factors

Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte's reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal d-factor of a graph. However, if we require that the d-factor is connected, these problems become NP-hard - finding a minimal connected 2-factor is just the traveling salesman problem (TSP). Given a complete graph with edge weights that satisfy the triangle inequality, we consider the problem of finding a minimal connected $d$-factor. We give a 3-approximation for all $d$ and improve this to an (r+1)-approximation for even d, where r is the approximation ratio of the TSP. This yields a 2.5-approximation for even d. The same algorithm yields an (r+1)-approximation for the directed version of the problem, where r is the approximation ratio of the asymmetric TSP. We also show that none of these minimization problems can be approximated better than the corresponding TSP. Finally, for the decision problem of deciding whether a given graph contains a connected d-factor, we extend known hardness results.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching

Belief propagation (BP) is a message-passing heuristic for statistical inference in graphical models such as Bayesian networks and Markov random fields. BP is used to compute marginal distributions or maximum likelihood assignments and has applications in many areas, including machine learning, image processing, and computer vision. However, the theoretical understanding of the performance of BP is unsatisfactory. Recently, BP has been applied to combinatorial optimization problems. It has been proved that BP can be used to compute maximum-weight matchings and minimum-cost flows for instances with a unique optimum. The number of iterations needed for this is pseudo-polynomial and hence BP is not efficient in general. We study belief propagation in the framework of smoothed analysis and prove that with high probability the number of iterations needed to compute maximum-weight matchings and minimum-cost flows is bounded by a polynomial if the weights/costs of the edges are randomly perturbed. To prove our upper bounds, we use an isolation lemma by Beier and Vöcking (SIAM J. Comput. 2006) for matching and generalize an isolation lemma for min-cost flow by Gamarnik, Shah, and Wei (Operations Research, 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Approximating Multi-Criteria TSP

We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP). First, we devise randomized approximation algorithms for multi-criteria maximum traveling salesman problems (Max-TSP). For multi-criteria Max-STSP, where the edge weights have to be symmetric, we devise an algorithm with an approximation ratio of 2/3 - eps. For multi-criteria Max-ATSP, where the edge weights may be asymmetric, we present an algorithm with a ratio of 1/2 - eps. Our algorithms work for any fixed number k of objectives. Furthermore, we present a deterministic algorithm for bi-criteria Max-STSP that achieves an approximation ratio of 7/27. Finally, we present a randomized approximation algorithm for the asymmetric multi-criteria minimum TSP with triangle inequality Min-ATSP. This algorithm achieves a ratio of log n + eps.

0 citations0 reviewsNo code linkedOpen access