We study the distributed minimum dominating set problem on graphs of arboricity α. Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-logarithmic approximation factor needs at least Ω(log Δ/log log Δ) rounds in graphs of maximum degree Δ and arboricity α, even when α = 2 and even when the message sizes are unbounded. Although there is a variety of algorithms with a near-optimal round complexity of O(log Δ), it is natural to ask: What is the best approximation factor in the optimal round complexity of O(log Δ/log log Δ)?

We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the (1,2)-TSP, where the distances between any two vertices are either one or two. Our primary emphasis is on the closely related Maximum Path Cover Problem, which aims to find a collection of vertex-disjoint paths that covers the maximum number of edges in a graph. We propose an algorithm that, for any ε > 0, achieves a (2/3-ε)-approximation of the maximum path cover size for an n-vertex graph, using poly(1/ε) passes. This result improves upon the previous 1/2-approximation by Behnezhad et al. [Soheil Behnezhad et al., 2023] in the semi-streaming model. Building on this result, we design a semi-streaming algorithm that constructs a tour for an instance of (1,2)-TSP with an approximation factor of (4/3 + ε), improving upon the previous 3/2-approximation factor algorithm by Behnezhad et al. [Soheil Behnezhad et al., 2023]. Furthermore, we extend our approach to develop an approximation algorithm for the Maximum TSP (Max-TSP), where the goal is to find a Hamiltonian cycle with the maximum possible weight in a given weighted graph G. Our algorithm provides a (7/12 - ε)-approximation for Max-TSP in poly(1/(ε)) passes, improving on the previously known (1/2-ε)-approximation obtained via maximum weight matching in the semi-streaming model.

We define the “relative” fractional independence number of a graph$G$with respect to another graph$H$, as where the maximum is taken over all graphs$W$.,$G \boxtimes W$is the strong product of$G$and$W$, and$\alpha$denotes the independence number. We give a nontrivial linear program to compute$\alpha^{*}(G\vert H)$, and discuss some of its properties. We show that$\alpha^{*}(G\vert H) \geq \frac{X(G)}{X(H)}\geq-\frac{1}{\alpha^{*}(H\vert G)}$, where$X(G)$can be the independence number, the Shannon capacity, the fractional independence number, the Lovász number, or the Schrijver's or Szegedy's variants of the Lovász number of a graph$G$, This inequality is the first explicit nontrivial upper bound on the ratio of the invariants of two arbitrary graphs, as mentioned earlier, which can also be used to obtain upper or lower bounds for these invariants. As explicit applications, we present new upper bounds for the ratio of the Shannon capacity of two Cayley graphs and compute new lower bounds on the Shannon capacity of certain Johnson graphs (yielding the exact value of their Haemers number). Moreover, we show that$\alpha^{*}(G\vert H)$can be used to present a stronger version of the well-known No-Homomorphism Lemma.

We present a novel family of simplicial complexes associated with the graph coloring problem. They include many well-known simplicial complexes such as chessboard complexes and crosspolytopes. We then study conditions under which these complexes become vertex decomposable and hence shellable. The connectivity of these complexes is also investigated. We apply these results to Tverberg's theorem with constraints and also to the chromatic number of certain Kneser-type hypergraphs and improve upon existing facts. Notably, we prove a conjecture of Engström and Norén on Tverberg graphs.

Computer-assisted collaborative peer grading is a developing growth area in academic evaluation. However, peer assessment often needs help with problems such as the lack of reliability, transparency, fairness, grading speed, and motivation to participate among students. The literature suggests several principles that each partly address the said issues. We propose a novel decentralized approach to academic peer assessment, using blockchain as an underlying technology, to address the principal problems in traditional peer assessment. We also derive design concepts for a modern courseware (CW) application consisting of our method and apply them to implement our approach in a CW called Blockment. We test the effectiveness of our method and system by running quantitative and qualitative experiments, proving our claims of improving reliability, transparency, fairness, grading speed, and motivation of grades in peer assessment. The results suggest embedding our method and system in academic courses to improve conventional peer grading methods.

Uncertainty about data appears in many realworld applications and an important issue is how to manage, analyze and solve optimization problems over such data. An important tool for data analysis is clustering. When the data set is uncertain, we can model them as a set of probabilistic points each formalized as a probability distribution function which describes the possible locations of the points. In this paper, we study k-center problem for probabilistic points in a general metric space. First we present a fast greedy approximation algorithm that builds k centers using a farthest-first traversal in k iterations. This algorithm improves the previous approximation factor of the unrestricted assigned k-center problem from 10 (see [1]) to 6. Next we restrict the centers to be selected from all the probabilistic locations of the given points and we show that an optimal solution for this restricted setting is a 2-approximation factor solution for an optimal solution of the assigned k-center problem with expected distance assignment. Using this idea, we improve the approximation factor of the unrestricted assigned k-center problem to 4 by increasing the running time. The algorithm also runs in polynomial time when k is a constant. Additionally, we implement our algorithms on three real data sets. The experimental results show that in practice the approximation factors of our algorithms are better than in theory for these data sets. Also we compare the results of our algorithm with the previous works and discuss about the achieved results.

In this paper, we present a randomized LOCAL constant approximation factor algorithm for minimum dominating set (MDS) problem and minimum total dominating set (MTDS) problem in graphs. The approximation factor of this algorithm for planar graphs with no 4-cycles is 18 and 9 for MDS and MTDS problems, respectively.

In real applications, there are situations where we need to model some problems based on uncertain data. This leads us to define an uncertain model for some classical geometric optimization problems and propose algorithms to solve them. The assigned version of the k-center problem for n uncertain points in a metric space is studied in this paper. The main approach is to replace each uncertain point with a clever choice of a certain point. We argue that the k-center solution for these certain replacements of our uncertain points, is a good constant approximation factor for the original uncertain k-center problem. This approach enables us to present fast and simple algorithms that give 10-approximation solution for the k-center problem in any metric space and when the ambient space is Euclidean, it can be improved to (3+ε)-approximation for any ε>0. These algorithms improve both the approximation factor and the running time of the previously known algorithms. Also, our algorithms are suitable for applying in the case of streaming and big data.