Search

We study the price of anarchy in graph coloring games (a subclass of polymatrix common-payoff games). Players are vertices of an undirected graph, and the strategies for each player are the colors \begin{document} $\left\{ {1, \ldots ,k} \right\}$ \end{document} . A tight bound of \begin{document} $\frac{k}{k-1}$ \end{document} is known (Hoefer 2007, Kun et al. 2013), if each player's payoff is the number of neighbors with different color than herself. In our generalization, payoff is computed by determining the distance of the player's color to the color of each neighbor, applying a concave function \begin{document} $f$ \end{document} to each distance, and then summing up the resulting values. This is motivated, e. g., by spectrum sharing, and includes the payoff functions suggested by Kun et al. (2013) for future work as special cases. Denote \begin{document} $f^*$ \end{document} the maximum value that \begin{document} $f$ \end{document} attains on \begin{document} $\left\{ {0, \ldots ,k - 1} \right\}$ \end{document} . We prove an upper bound of \begin{document} $2$ \end{document} on the price of anarchy if \begin{document} $f$ \end{document} is non-decreasing or assumes \begin{document} $f^*$ \end{document} somewhere in \begin{document} $\left\{ {0, \ldots ,{\frac{k}{2}}} \right\}$ \end{document} . Matching lower bounds are given for the monotone case and if \begin{document} $f^*$ \end{document} is assumed in \begin{document} $\frac{k}{2}$ \end{document} for even \begin{document} $k$ \end{document} . For general concave \begin{document} $f$ \end{document} , we prove an upper bound of \begin{document} $3$ \end{document} . We use a new technique that works by an appropriate splitting \begin{document} $\lambda = \lambda_1 + \ldots + \lambda_k$ \end{document} of the bound \begin{document} $\lambda$ \end{document} we are proving.

Background For single-cell or metagenomic sequencing projects, it is necessary to sequence with a very high mean coverage in order to make sure that all parts of the sample DNA get covered by the reads produced. This leads to huge datasets with lots of redundant data. A filtering of this data prior to assembly is advisable. Brown et al. (2012) presented the algorithm Diginorm for this purpose, which filters reads based on the abundance of their k-mers. Methods We present Bignorm, a faster and quality-conscious read filtering algorithm. An important new algorithmic feature is the use of phred quality scores together with a detailed analysis of the k-mer counts to decide which reads to keep. Results We qualify and recommend parameters for our new read filtering algorithm. Guided by these parameters, we remove in terms of median 97.15% of the reads while keeping the mean phred score of the filtered dataset high. Using the SDAdes assembler, we produce assemblies of high quality from these filtered datasets in a fraction of the time needed for an assembly from the datasets filtered with Diginorm. Conclusions We conclude that read filtering is a practical and efficient method for reducing read data and for speeding up the assembly process. This applies not only for single cell assembly, as shown in this paper, but also to other projects with high mean coverage datasets like metagenomic sequencing projects. Our Bignorm algorithm allows assemblies of competitive quality in comparison to Diginorm, while being much faster. Bignorm is available for download at https://git.informatik.uni-kiel.de/axw/Bignorm. Electronic supplementary material The online version of this article (doi:10.1186/s12859-017-1724-7) contains supplementary material, which is available to authorized users.

We present an extension to nonatomic congestion games (NCG). An NCG models a large number of players depending on a set of resources (e.g., network links) in certain combinations (e.g., paths or multicast trees) called strategies. The rate of consumption ZeS specifies how aggressively resource e is consumed when used via strategy S, but it also effects how strongly the resource's latency is experienced by the players. Our extension allows essentially unrelated factors CeS and ReS instead of ZeS. Factor CeS is the actual rate of consumption, whereas ReS expresses the amplification of the resource latency of e for players choosing strategy S, or, in other words, the relevance of resource e for strategy S. We call the extended model nonatomic consumption-relevance congestion games (NCRCG). NCRCGs exhibit new phenomena, including multiple Nash equilibria of different social cost and—even from a worst-case point of view—a dependence of the price of anarchy on structural parameters not limited to the class of resource latency functions used. We prove almost tight lower, upper, and bicriteria bounds for the price of anarchy for polynomial latency functions with nonnegative coefficients. We conjecture that the lower bound is the best possible. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

Als erstes Schwerpunktprogramm bekommt das DFG SPP 1307 ,,Algorithm Engineering“ durch deutsch-indische Projekte eine binationale Komponente. Die Zusammenarbeit in der 3. Phase des Schwerpunktprogrammes umfasst Optimierung im Schienenverkehr, Berechnungen unter Unsicherheiten, Algorithmen fur Datenstrome und parallele quantum-evolutionare Algorithmen.

In this model of network formation, players anticipate the destruction of one link, which is chosen according to a known probability distribution. Their cost is the cost for building links plus the expected number of other players to which connection will be lost as a result of the link destruction. We consider different equilibrium concepts (Nash equilibrium, pairwise Nash equilibrium, pairwise stability) and two different ways in which the probability distribution depends on the network.

We present the first deterministic 1+e approximation algorithm for finding a large matching in a bipartite graph in the semi-streaming model which requires only O((1/e)5) passes over the input stream. In this model, the input graph G=(V,E) is given as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(npolylog n) bits, where $n = \lvert {V}\rvert $. The only previously known arbitrarily good approximation for general graphs is achieved by the randomized algorithm of McGregor (Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Randomization and Computation, Berkeley, CA, USA, pp. 170–181, 2005), which uses Ω((1/e)1/e ) passes. We show that even for bipartite graphs, McGregor’s algorithm needs Ω(1/e) Ω(1/e) passes, thus it is necessarily exponential in the approximation parameter. The design as well as the analysis of our algorithm require the introduction of some new techniques. A novelty of our algorithm is a new deterministic assignment of matching edges to augmenting paths which is responsible for the complexity reduction, and gets rid of randomization. We repeatedly grow an initial matching using augmenting paths up to a length of 2k+1 for k=⌈2/e⌉. We terminate when the number of augmenting paths found in one iteration falls below a certain threshold also depending on k, that guarantees a 1+e approximation. The main challenge is to find those augmenting paths without requiring an excessive number of passes. In each iteration, using multiple passes, we grow a set of alternating paths in parallel, considering each edge as a possible extension as it comes along in the stream. Backtracking is used on paths that fail to grow any further. Crucial are the so-called position limits: when a matching edge is the ith matching edge in a path and it is then removed by backtracking, it will only be inserted into a path again at a position strictly lesser than i. This rule strikes a balance between terminating quickly on the one hand and giving the procedure enough freedom on the other hand.

The development of efficient 3D seed reconstruction algorithms is an ongoing and vivid research topic. Since the 1980s many publications about seed assignment were published. In this paper a novel mathematical approach is described to solve the 3D assignment problem for the reconstruction of seeds with radiographs: we present a fast linear programming approach together with afterwards applying the so-called randomized rounding scheme to compute good (possibly partial) assignments. We apply a visualization software that allows user interaction to check the solution given by the algorithm and to augment partial assignments. The second step is justified as the randomized algorithm already returns optimal solutions is many cases, and in cases with partial assignments it fails to match only a very small number of seed images. Our algorithm transfers ideas from recent breakthrough research work on the design of efficient randomized algorithms in discrete optimization and computer science to the seed reconstruction problem.

We present practical approaches for low-discrepancy 2-colorings in the hypergraph of arithmetic progressions. A simple randomized algorithm, a deterministic combinatorial algorithm (Sarkozy 1974), and three estimation of distribution algorithms are compared. The best of them experimentally achieves a constant-factor approximation.

We present a new quantum-inspired evolutionary algorithm, the attractor population QEA (apQEA). Our benchmark problem is a classical and difficult problem from Combinatorics, namely finding low-discrepancy colorings in the hypergraph of arithmetic progressions on the first n integers, which is a massive hypergraph (e.g., with approx. 3.88 ×1011 hyperedges for n = 250 000). Its optimal low-discrepancy coloring bound \(\Theta(\sqrt[4]{n})\) is known and it has been a long-standing open problem to give practically and/or theoretically efficient algorithms. We show that apQEA outperforms known QEA approaches and the classical combinatorial algorithm (Sarkozy 1974) by a large margin. Regarding practicability, it is also far superior to the SDP-based polynomial-time algorithm of Bansal (2010), the latter being a breakthrough work from a theoretical point of view. Thus we give the first practical algorithm to construct optimal colorings in this hypergraph, up to a constant factor. We hope that our work will spur further applications of Algorithm Engineering to Combinatorics.

We study network formation with the bilateral link formation rule (Jackson and Wolinsky 1996) with $n$ players and link cost $\alpha>0$. After the network is built, an adversary randomly destroys one link according to a certain probability distribution. Cost for player $v$ incorporates the expected number of players to which $v$ will become disconnected. This model was previously studied for unilateral link formation (K. 2011). We prove existence of pairwise Nash equilibria under moderate assumptions on the adversary and $n\geq 9$. As the main result, we prove bounds on the price of anarchy for two special adversaries: one destroys a link chosen uniformly at random, while the other destroys a link that causes a maximum number of player pairs to be separated. We prove bounds tight up to constants, namely $O(1)$ for one adversary (if $\alpha>1/2$), and $\Theta(n)$ for the other (if $\alpha>2$ considered constant and $n \geq 9$). The latter is the worst that can happen for any adversary in this model (if $\alpha=\Omega(1)$)., Comment: 6th International Symposium on Algorithmic Game Theory (SAGT 2013)

We present a model for distributed network formation with cost expressing robustness in an adversary model. There are n players, each representing a vertex. Players may establish links to other players, building a link incurs a cost α. Individual cost comprises this building cost plus an indirect cost. After the network is built, an adversary deletes one link. The adversary is modeled by a random experiment, specified by a probability distribution on the links. Players know this distribution. Indirect cost for player v is the expected number of players to which v will become disconnected when the adversary strikes. We can prove an O(1) bound on the price of anarchy for two different adversaries under unilateral link formation. Under bilateral link formation, we can prove an O(1+√n/α) bound for one adversary, and for the other an asymptotically tight Ω(n) bound if α = Θ(1).

We give an overview of important results for non-atomic congestion games in their traditional form along with self-contained and short proofs and then present new results and challenges for an extended model, which we call consumption-relevance congestion games . We introduce the consumption-relevance congestion game first and show that all other models are special cases of it. Our focus is on the price of anarchy, computation of equilibria, and experimental studies. Further interesting aspects are summarized at the end of this article.

We present an algorithm for finding a large matching in a bipartite graph in the semi-streaming model. In this model, the input graph G = (V, E) is represented as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(n , polylog n) bits, where n = |V|. For e> 0, our algorithm finds a \(\frac{1}{1+\epsilon}\)-approximation of a maximum-cardinality matching and uses \(O{({(\frac{1}{\epsilon})^8})}\) passes over the input stream. The only previously known algorithm with such arbitrarily good approximation – though for general graphs – required exponentially many \(\Omega({{(\frac{1}{\epsilon})^{\frac{1}{\epsilon}}}})\) passes (McGregor 2005).

Brachytherapy is a radiotherapy method for cancer. In its low dose radiation (LDR) variant a number of radioactive implants, so-called seeds, are inserted into the affected organ through an operation. After the implantation, it is essential to determine the locations of the seeds in the organ. A common method is to take three X-ray photographs from different angles; the seeds show up on the X-ray photos as small white lines. In order to reconstruct the three-dimensional configuration from these X-ray photos, one has to determine which of these white lines belong to the same seed. We model the problem as a mixed packing and covering hypergraph optimization problem and present a randomized approximation algorithm based on linear programming. We analyse the worst-case performance of the algorithm by discrete probabilistic methods and present results for data of patients with prostate cancer from the university clinic of Schleswig-Holstein, Campus Kiel. These examples show an almost optimal performance of the algorithm which presently cannot be matched by the theoretical analysis.

The development of efficient 3D seed reconstruction algorithms is an ongoing and vivid research topic. Since the 1980s many publications about seed assignment were published. In this paper a novel mathematical approach is described to solve the 3D assignment problem for the reconstruction of seeds with radiographs: we present a fast linear programming approach together with afterwards applying the so-called randomized rounding scheme to compute good (possibly partial) assignments. We apply a visualization software that allows user interaction to check the solution given by the algorithm and to augment partial assignments. The second step is justified as the randomized algorithm already returns optimal solutions is many cases, and in cases with partial assignments it fails to match only a very small number of seed images. Our algorithm transfers ideas from recent breakthrough research work on the design of efficient randomized algorithms in discrete optimization and computer science to the seed reconstruction problem.

We study the price of anarchy for selfish multicast routing games in directed multigraphs with latency functions on the edges, extending the known theory for the unicast situation, and exhibiting new phenomena not present in the unicast model. In the multicast model we have N commodities (or player classes), where for each $ i=1,\hdots,N$, a flow from a source si to a finite number of terminals $t_i^1,\hdots,t_i^{k_i}$ has to be routed such that every terminal tij receives flow ni∈ℝ≥0. One of the significant results of this paper are upper and lower bounds on the price of anarchy for edge latencies being polynomials of degree at most p with non-negative coefficients. We show an upper bound of $(p+1)\cdot\frac{\nu^{p+1}}{\nu^*}$ in some variants of multicast routing. We also prove a lower bound of νp, so we have upper and lower bounds that are tight up to a factor of (p+1)ν. Here, ν and ν* are network and strategy dependent parameters reflecting the maximum/minimum consumption of the network. Both are 1 in the unicast case. Our lower bound of νp, where in the general situation we have ν>1, shows an exponential increase compared to the Roughgarden bound of O(p/lnp) for the unicast model. This exhibits the contrast to the unicast case, where we have Roughgarden’s (2002) result that the price of anarchy is independent of the network topology. To our knowledge this paper is the first thorough study of the price of anarchy in the multicast scenario. The approach may lead to further research extending game-theoretic network analysis to models used in applications.