Search

We propose a dynamic augmentation scheme for the asymptotic solution of the nonlinear algebraic loops arising in well-known input saturated feedbacks typically designed by solving linear matrix inequalities (LMIs). We prove that the existing approach based on dynamic augmentation, which replaces the static loop by a dynamic one through the introduction of a sufficiently small time constant, works under some restrictive sufficient well-posedness conditions, requiring the existence of a diagonal Lyapunov matrix. However it can fail in general, even when the algebraic loop is well-posed. Then, we propose a novel approach whose effectiveness is guaranteed whenever wellposedness holds. We also show how this augmentation allows preserving the guaranteed region of attraction with Lyapunovbased designs, as long as a gain parameter is sufficiently large. We finally propose an adaptive version of the scheme where this parameter is adjusted online. Simulation results show the effectiveness of the proposed solutions.

The goal of hyperspectral image analysis is often to determine which materials, out of a given set of possibilities, are present in each pixel. As hyperspectral data are being gathered in rapidly increasing amounts, automatic image analysis is becoming progressively more important. Automatic identification of materials from a mixed pixel is possible with 1) Bayesian unmixing algorithms and 2) multiobjective sparse unmixing algorithms when a method such as elbow estimation is used to select the best solution from the set of Pareto-optimal solutions. We develop a new elbow estimation method called termination condition adaptive elbow (TCAE) for selecting the best solution from the set of Pareto-optimal solutions to a biobjective unmixing problem. Specifically, the two objectives are assumed to be the sparsity level of the fractional abundance vector and the reconstruction error. We conduct experiments with real-world unmixing applications in mind, and TCAE performs significantly better than a state-of-the-art elbow estimation method when they are both used to select the best solution from the sequence of fractional abundance vectors generated by iterative spectral mixture analysis (ISMA). Furthermore, the combination of ISMA and TCAE is able to identify endmembers from mixed pixels several times faster and with higher F1-score than the two Bayesian unmixing algorithms used as a reference. We conclude that the combination of ISMA and TCAE facilitates automatic, reliable, and rapid identification of endmembers from mixed pixels.

We develop a new algorithm for activity detection for grant-free multiple access in distributed multiple-input multiple-output (MIMO). The algorithm is a distributed version of the approximate message passing (AMP) based on a soft combination of likelihood ratios computed independently at multiple access points. The underpinning theoretical basis of our algorithm is a new observation that we made about the state evolution in the AMP. Specifically, with a minimum mean-square error denoiser, the state maintains a block-diagonal structure whenever the covariance matrices of the signals have such a structure. We show by numerical examples that the algorithm outperforms competing schemes from the literature., 5 pages, 2 figures. This paper has been accepted for publication in IEEE Wireless Communications Letters. Code available at https://github.com/jiananbai/distributed-AMP

We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

“I’m an MC still as honest” – Eminem, Rap God We present MCRapper , an algorithm for efficient computation of Monte-Carlo Empirical Rademacher Averages (MCERA) for families of functions exhibiting poset (e.g., lattice) structure, such as those that arise in many pattern mining tasks. The MCERA allows us to compute upper bounds to the maximum deviation of sample means from their expectations, thus it can be used to find both (1) statistically-significant functions (i.e., patterns) when the available data is seen as a sample from an unknown distribution, and (2) approximations of collections of high-expectation functions (e.g., frequent patterns) when the available data is a small sample from a large dataset. This flexibility offered by MCRapper is a big advantage over previously proposed solutions, which could only achieve one of the two. MCRapper uses upper bounds to the discrepancy of the functions to efficiently explore and prune the search space, a technique borrowed from pattern mining itself. To show the practical use of MCRapper , we employ it to develop an algorithm TFP-R for the task of True Frequent Pattern (TFP) mining, by appropriately computing approximations of the negative and positive borders of the collection of patterns of interest, which allow an effective pruning of the pattern space and the computation of strong bounds to the supremum deviation. TFP-R gives guarantees on the probability of including any false positives (precision) and exhibits higher statistical power (recall) than existing methods offering the same guarantees. We evaluate MCRapper and TFP-R and show that they outperform the state-of-the-art for their respective tasks.

We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r, so as to minimize the sum of the client waiting times, where the waiting time of a client v is the length of the r-v portion of P. We give the first constant-factor approximation guarantee for DirLat, but in quasi-polynomial time. Previously, a polynomial-time O(log n)-approximation was known [Z. Friggstad et al., 2013], and no better approximation guarantees were known even in quasi-polynomial time. A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of [A. Köhne et al., 2019] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant, which itself builds on the breakthrough similar result established for asymmetric TSP (ATSP) by Svensson et al. [O. Svensson et al., 2018]. We show that the integrality gap of the Held-Karp relaxation for ATSPP is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from x(δ^{in}(S)) ≥ 1 to x(δ^{in}(S)) ≥ ρ for some constant 1/2 < ρ ≤ 1. We also give a better approximation guarantee for the minimum total-regret problem, where the goal is to find a path P that minimizes the total time that nodes spend in excess of their shortest-path distances from r, which can be cast as a special case of DirLat involving so-called regret metrics.

Many discrete optimization problems amount to selecting a feasible set of edges of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances of the chosen set of edges for the worst positions of the vertices in their uncertainty sets. We first prove that these problems are [Formula: see text]-hard even when the feasible sets consist either of all spanning trees or of all s – t paths. Given this hardness, we propose an exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be solved efficiently. We also propose a conservative approximation and show its equivalence to the affine decision rule approximation in the context of Euclidean distances. We compare our algorithms to three deterministic reformulations on instances inspired by the scientific literature for the Steiner tree problem and a facility location problem. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.1276 .

This paper proposes a general formulation for temporal parallelisation of dynamic programming for optimal control problems. We derive the elements and associative operators to be able to use parallel scans to solve these problems with logarithmic time complexity rather than linear time complexity. We apply this methodology to problems with finite state and control spaces, linear quadratic tracking control problems, and to a class of nonlinear control problems. The computational benefits of the parallel methods are demonstrated via numerical simulations run on a graphics processing unit., Comment: To appear in IEEE Transactions on Automatic Control

We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a $2$-edge-connected spanning subgraph by adding the minimum number of edges to it. We present a polynomial-time algorithm with an approximation ratio of $13/8 = 1.625$ improving upon an earlier $5/3$-approximation. The improvement builds on a new $\alpha$-approximation preserving reduction for any $\alpha\geq 3/2$ from arbitrary MAP instances to well-structured instances that do not contain certain forbidden structures like parallel edges, small separators, and contractible subgraphs. We further introduce, as key ingredients, the technique of repeated simultaneous contractions and provide improved lower bounds for instances that cannot be contracted., Comment: 60 pages, 16 figures. Accepted at ICALP 2023

For any $\varepsilon > 0$, we give a polynomial-time $n^\varepsilon$-approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O(1)$-sequence. This result is derived from the following time-approximation trade-off: We establish an $O(1)^{2^q-1}$-approximation algorithm running in time $\exp(O_q(n^{2^{-q}}))$, for every integer $q \geqslant 0$. Guided by the same framework, we obtain similar approximation algorithms for Min Coloring and Max Induced Matching. In general graphs, all these problems are known to be highly inapproximable: for any $\varepsilon > 0$, a polynomial-time $n^{1-\varepsilon}$-approximation for any of them would imply that P$=$NP [Hastad, FOCS '96; Zuckerman, ToC '07; Chalermsook et al., SODA '13]. We generalize the algorithms for Max Independent Set and Max Induced Matching to the independent (induced) packing of any fixed connected graph $H$. In contrast, we show that such approximation guarantees on graphs of bounded twin-width given with an $O(1)$-sequence are very unlikely for Min Independent Dominating Set, and somewhat unlikely for Longest Path and Longest Induced Path. Regarding the existence of better approximation algorithms, there is a (very) light evidence that the obtained approximation factor of $n^\varepsilon$ for Max Independent Set may be best possible. This is the first in-depth study of the approximability of problems in graphs of bounded twin-width. Prior to this paper, essentially the only such result was a~polynomial-time $O(1)$-approximation algorithm for Min Dominating Set [Bonnet et al., ICALP '21]., 32 pages, 3 figures, 1 table

We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set $S$ of points and a set $\mathcal{R}$ of geometric objects, and the goal is to find a subset $\mathcal{R}^*\subseteq\mathcal{R}$ to cover all points in $S$ such that the \textit{membership} of $S$ with respect to $\mathcal{R}^*$, denoted by $\mathsf{memb}(S,\mathcal{R}^*)$, is minimized, where $\mathsf{memb}(S,\mathcal{R}^*)=\max_{p\in S}|\{R\in\mathcal{R}^*: p\in R\}|$. We achieve the following two main results. * We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time $n^{O(\mathsf{opt})}$ where $\mathsf{opt}$ is the optimum of the problem (i.e., the minimum membership). * We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of $o(\log n)$ in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find $\mathcal{R}^*\subseteq\mathcal{R}$ to cover $S$ such that the ply of $\mathcal{R}^*$ is minimized, where the ply is defined as the maximum number of objects in $\mathcal{R}^*$ which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in $O(n^{12})$ time. We give a significantly simpler constant-approximation algorithm with near-linear running time., Comment: In SoCG'23

In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the "virtual machine packing" problem on trees studied by Sindelar et al. [SPAA'11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks'12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of "reduced length"., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 27:1-27:16

We give a classical $1/(qk+1)$-approximation for the maximum eigenvalue of a $k$-sparse fermionic Hamiltonian with strictly $q$-local terms, as well as a $1/(4k+1)$-approximation when the Hamiltonian has both $2$-local and $4$-local terms. More generally we obtain a $1/O(qk^2)$-approximation for $k$-sparse fermionic Hamiltonians with terms of locality at most $q$. Our techniques also yield analogous approximations for $k$-sparse, $q$-local qubit Hamiltonians with small hidden constants and improved dependence on $q$., Comment: 6 pages, No Figures, edited typos and added additional details on the qubit results, accepted to TQC2023

The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum k-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of weak Szemerédi regularity lemmas for k-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop constant time sampling algorithms, and to characterize the "vertex sample complexity" of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 20:1-20:18

We present an O(log k)-approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where k is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree, in which we get a O(R+log k)-approximation for planar graphs for where R is the number of roots., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 63:1-63:14

Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis - including potential functions and primal-dual techniques - give insight into this still-growing area. Here, we introduce a new analysis technique that first uses a potential function to upper bound the cost of an online algorithm and then pairs that with a new dual-fitting strategy to lower bound the cost of an offline optimal algorithm. We apply these techniques to the Caching with Reserves problem recently introduced by Ibrahimpur et al. [Ibrahimpur et al., 2022] and give an O(log k)-competitive fractional online algorithm via a marking strategy, where k denotes the size of the cache. We also design a new online rounding algorithm that runs in polynomial time to obtain an O(log k)-competitive randomized integral algorithm. Additionally, we provide a new, simple proof for randomized marking for the classical unweighted paging problem., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 80:1-80:20

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ(G) ≤ n/2, the length of the longest cycle L is at least 2δ(G). Thus the "essential" part of finding the longest cycle is in approximating the "offset" k = L - 2δ(G). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2δ(G)+Ω(f(k))., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 60:1-60:18

Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results: - A self-stabilizing 2(1+ε)-approximation algorithm for minimum weight vertex cover that converges in O(logΔ /(εlog log Δ)) synchronous rounds. - A self-stabilizing Δ-approximation algorithm for maximum weight independent set that converges in O(Δ+log^* n) synchronous rounds. - A self-stabilizing ((2ρ+1)(1+ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((logΔ)/ε) synchronous rounds. In all of the above, Δ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set., LIPIcs, Vol. 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022), pages 27:1-27:19

In 1982, Papadimitriou and Yannakakis introduced the Exact Matching (EM) problem where given an edge colored graph, with colors red and blue, and an integer k, the goal is to decide whether or not the graph contains a perfect matching with exactly k red edges. Although they conjectured it to be NP-complete, soon after it was shown to be solvable in randomized polynomial time in the seminal work of Mulmuley et al., placing it in the complexity class RP. Since then, all attempts at finding a deterministic algorithm for EM have failed, thus leaving it as one of the few natural combinatorial problems in RP but not known to be contained in P, and making it an interesting instance for testing the hypothesis RP = P. Progress has been lacking even on very restrictive classes of graphs despite the problem being quite well known as evidenced by the number of works citing it. In this paper we aim to gain more insight into EM by studying a new optimization problem we call Top-k Perfect Matching (TkPM) which we show to be polynomially equivalent to EM. By virtue of being an optimization problem, it is more natural to approximate TkPM so we provide approximation algorithms for it. Some of the approximation algorithms rely on a relaxation of EM on bipartite graphs where the output is required to be a perfect matching with a number of red edges differing from k by at most k/2, which is of independent interest and generalizes to the Exact Weight Perfect Matching (EWPM) problem. We also consider parameterized algorithms and show that TkPM can be solved in FPT time parameterized by k and the independence number of the graph. This result again relies on new tools developed for EM which are also of independent interest., Leibniz International Proceedings in Informatics (LIPIcs), 254, ISSN:1868-8969, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), ISBN:978-3-95977-266-2

We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given a set of n unit size precedence-ordered jobs, and a set of m related machines each with size m_i (machine i can execute at most m_i jobs at any time). Each machine i has an associated in-delay ρ^{in}_i and out-delay ρ^{out}_i. Each job v also has an associated in-delay ρ^{in}_v and out-delay ρ^{out}_v. In a schedule, job v may be executed on machine i at time t if each predecessor u of v is completed on i before time t or on any machine j before time t - (ρ^{in}_i + ρ^{out}_j + ρ^{out}_u + ρ^{in}_v). The objective is to construct a schedule that minimizes makespan, which is the maximum completion time over all jobs. We consider schedules which allow duplication of jobs as well as schedules which do not. When duplication is allowed, we provide an asymptotic polylog(n)-approximation algorithm. This approximation is further improved in the setting with uniform machine speeds and sizes. Our best approximation for non-uniform delays is provided for the setting with uniform speeds, uniform sizes, and no job delays. For schedules with no duplication, we obtain an asymptotic polylog(n)-approximation for the above model, and a true polylog(n)-approximation for symmetric machine and job delays. These results represent the first polylogarithmic approximation algorithms for scheduling with non-uniform communication delays. Finally, we consider a more general model, where the delay can be an arbitrary function of the job and the machine executing it: job v can be executed on machine i at time t if all of v’s predecessors are executed on i by time t-1 or on any machine by time t - ρ_{v,i}. We present an approximation-preserving reduction from the Unique Machines Precedence-constrained Scheduling (umps) problem, first defined in [Sami Davies et al., 2022], to this job-machine delay model. The reduction entails logarithmic hardness for this delay setting, as well as polynomial hardness if the conjectured hardness of umps holds. This set of results is among the first steps toward cataloging the rich landscape of problems in non-uniform delay scheduling., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 98:1-98:20

This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfaction problems (CSPs), which are considered to be one of the most fundamental problems in theoretical computer science. The first class of problems studied in this thesis consists of some Boolean CSPs with cardinality constraints. A cardinality constraint for an instance of a Boolean CSP restricts assignments to have a certain number of variables assigned to 1 and 0. Assuming the Unique Games Conjecture, we show that Max-Cut with cardinality constraints is hard to approximate within approximately 0.858, and that Max-2-Sat with cardinality constraints is hard to approximate within approximately 0.929. The same inapproximability ratio as for cardinality constrained Max-2-Sat is obtained for the cardinality-constrained Vertex Cover problem, known as Max-k-VC. We also examine regular constraint satisfaction problems where each variable in an instance has the same number of occurrences. We investigate approximability of such problems and show that for any CSP Λ, the existence of an α-approximation algorithm for regular Max-CSP Λ implies the existence of an (α − o(1))-approximation algorithm for weighted Max-CSP Λ for which the regularity of instances is not imposed. We also give an analogous result for Min-CSPs. In particular, if one is not interested in lower-order terms, we show that the study of the approximability of CSPs can be conducted solely on regular instances. We also consider approximability of Max-3-Lin problems over non-Abelian groups in a universal factor graph setting. The factor graph of an instance with n variables and m constraints is the bipartite graph between [m] and [n], in which edges connect constraints with the variables they contain. The universal factor graph setting assumes that a factor graph for an instance is fixed for each input size. Building on the previous works, we show optimal inapproximability of Max-3-Lin problems over non-Abelian groups in the universal factor graph setting, both in the case of perfect and almost perfect completeness. We also show that these hardness results apply in the setting in which linear equations in the Max-3-Lin problem are restricted to the form x · y · z = g, where x, y, z are variables and $g$ is a group element, in contrast to previous works where constants have appeared on the left side of the equations as well. Finally, we study the approximability of the Minimum Sum Vertex Cover problem, in which we are given a graph as an input and the goal is to find anordering of vertices that minimizes the total cover time of edges. An edge is covered when one of its endpoints is visited in an ordering, and the covertime for the edge is exactly the time that the endpoint is visited. In this work, we give the first explicit hardness of approximation result and show that Minimum Sum Vertex Cover can not be approximated below 1.0748, assuming the Unique Games Conjecture. Furthermore, we study Minimum Sum Vertex Cover on regular graphs and demonstrate an inapproximability ratio of 1.0157. By revisiting an algorithm introduced by Feige, Lov\'{a}sz, and Tetali, we also show approximability within 1.225 for regular graphs. Denna avhandling undersöker hur approximerbarheten av vissa grundläggande datavetenskapliga problem på verkas av ytterligare krav på strukturen hos indata. De studerade problemen tillhör eller är nära relaterade till Constraint Satisfaction Problems (CSPs), som anses vara ett av de mest grundläggande problemen inom teoretisk datavetenskap. Den första problemklassen som studeras i denna avhandling består av vissa Booleska CSPs med kardinalitetsbegränsningar. En kardinalitetsbegränsning för en instans av en Boolesk CSP begränsar tilldelningarna att ha ett visst antal variabler tilldelade till 1 och 0. Under antagandet att Unique Games Conjecture gäller, visar vi att Max-Cut med kardinalitetsbegränsningar är svårt att approximera inom cirka 0.858, och att Max-2-Sat med kardinalitetsbegränsningar är svårt att approximera inom cirka 0.929. Samma approximationsförhållande som för kardinalitetsbegränsad Max-2-Sat erhålls för kardinalitetsbegrän sade versionen av Vertex Cover-problemet, känd som Max-k-VC. Vi undersöker också regelbundna begränsningsproblem där varje variabel i en instans har samma antal förekomster. Vi undersöker approximabiliteten för sådana problem och visar att för något CSP Λ så innebär existensen av en α-approximationsalgoritm för regelbundet Max-CSP Λ existensen av en (α − o(1))-approximationsalgoritm för viktade Max-CSP Λ där regelbundenheten för instanserna inte nödvändigtvis är uppfyllt. Vi ger också ett analogt resultat för Min-CSPs. Särskilt visar vi att om man inte är intresserad av termer med lägre ordning så kan undersökningen av approximabiliteten för CSPs utföras enbart på regelbundna instanser. Vi undersöker även approximerbarheten hos Max-3-Lin problemen över icke-Abelska grupper med universell faktorgraf. Faktorgrafen för en instans med n variabler och m begränsningar är den bipartita grafen mellan [m] och [n] där kanterna kopplar begränsningar till variabler som de innehåller. Den universella faktorgrafen antar att en faktorgraf för en instans är fixerad för varje indatastorlek. Med utgångspunkt från tidigare arbeten visar vi optimal inapproximerbarhet av Max-3-Lin problemet över icke-Abelska grupper med universella faktorgrafer, både i fallet med perfekt och nästan perfekt fullständighet. Vi visar också att dessa svårighetsresultat gäller i fallet där linjära ekvationer i Max-3-Lin problemet är begränsade till formen x·y·z = g, där x, y, z är variablerna och g är ett gruppelement, till skillnad från tidigare arbeten där konstanter även har förekommit på vänster sida av ekvationerna. Slutligen studerar vi approximabiliteten av Minimum Sum Vertex Cover-problemet, där vi får en graf som indata och målet är att hitta en ordning av hörn som minimerar den totala övertäcktningsiden för kanter. En kant täcks när en av dess ändpunkter besöks i en beställning, och omslaget tid för kanten är exakt den tidpunkt då ändpunkten besöks i ordningen. I detta arbete ger vi det första explicita resultatet för svårighetsgraden av approximering och visar att Minimum Sum Vertex Cover inte kan approximeras nedanför 1.0748, under antagandet om Unique Games Conjecture. Vidare studerar vi Minimum Sum Certex Cover på regelbundna grafer och visar en inapproximationskvot på 1.0157. Genom att återbesöka en algoritm föreslagen av Feige, Lovász och Tetali, visar vi också approximerbarhet inom 1.225 för regelbundna grafer. QC 2023-05-08

In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2+ε)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22]., LIPIcs, Vol. 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), pages 63:1-63:13

Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements (such as nodes or links). One such problem is Connectivity Augmentation, with the goal of cheaply increasing the (edge- or node-)connectivity of a given network from a value k to $$k+1$$ k + 1 . The problem is NP-hard for $$k \ge 1$$ k ≥ 1 , and the most studied setting focuses on the case of edge-connectivity with $$k=1$$ k = 1 . In this work, we give a 1.892-approximation algorithm for the NP-hard problem of augmenting the node-connectivity of any given graph from 1 to 2, which improves upon the state-of-the-art approximation previously developed in the literature. The starting point of our work is a known reduction from Connectivity Augmentation to some specific instances of the Node-Steiner Tree problem, and our result is obtained by developing a new and simple analysis of the iterative randomized rounding technique when applied to such Steiner Tree instances. Our results also imply a 1.892-approximation algorithm for the problem of augmenting the edge-connectivity of a given graph from any value k to $$k+1$$ k + 1 . While this does not beat the best approximation factor known for this problem, a key point of our work is that the analysis of our approximation factor is less involved when compared to previous results in the literature. In addition, our work gives new insights on the iterative randomized rounding method, that might be of independent interest.

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which we are given $m$ agents, $n$ indivisible resources, and we have to allocate resources in order to maximize the happiness of the least happy agent. For the network design part, we study two key problems: the Steiner Forest problem and the Matching Augmentation problem. In the first part of this thesis, we give improved guarantees for the Santa Claus problem in two prominent settings. First, we consider the Santa Claus problem in the setting where the happiness of each agent $i$ is an arbitrary linear function $f_i$. Obtaining a constant factor approximation in that setting is a major open problem in the area of approximation algorithms. In 2009, the MaxMin Arborescences problem was identified as a key special case that appears to capture most of the difficulty of the general problem. Even in that special case, a constant factor approximation has remained elusive, and the current best algorithm only guarantees a polylogarithmic approximation in quasi-polynomial time. We give an exponential improvement to this, an $O(\textrm{poly}(\log \log (n)))$-approximation in quasi-polynomial time for the MaxMin Arborescences problem. Our second result in this part considers the Santa Claus problem in the restricted assignment case: all the agents have the same happiness function $f$, but each agent $i$ is only interested in a subset $\Gamma_i$ of the resources. When $f$ is a monotone submodular function, we show that we can obtain an $O(\log \log n)$-approximation in polynomial time. Before our work, comparable results in this setting were only known for the case where $f$ is a linear function. In the second part of this thesis, we start with the Steiner Forest problem which is defined as follows. Given a graph $G$ and an arbitrary set of $k$ terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k\}\}$, the goal is to return a minimum-weight subgraph that connects all the pairs. In 1996, Awerbuch, Azar, and Bartal showed that an intuitive greedy algorithm guarantees an $O(\log^2 k)$-approximation. Our first result is to show that, in fact, the greedy algorithm guarantees an $O(\log (k)\cdot \log \log (k))$-approximation, which is nearly tight in light of a known lower bound of order $\Omega(\log k)$. Interestingly, our analysis also gives important insights in the online setting of the problem, in which the pairs are revealed one by one in an adversarial order. Our last result is on the Matching Augmentation problem, a key problem to compute cheap $2$-edge connected subgraphs. We give a simple polynomial time algorithm that guarantees a better-than-$2$ approximation when compared to the standard relaxation of the problem known as the cut LP. In contrast, previous better-than-$2$ approximations were much more complicated and did not compare to this simple relaxation.

We propose a linear programming method that is based on active-set changes and proximal-point iterations. The method solves a sequence of least-distance problems using a warm-started quadratic programming solver that can reuse internal matrix factorizations from the previously solved least-distance problem. We show that the proposed method terminates in a finite number of iterations and that it outperforms state-of-the-art LP solvers in scenarios where an extensive number of small/medium scale LPs need to be solved rapidly, occurring in, for example, multi-parametric programming algorithms. In particular, we show how the proposed method can accelerate operations such as redundancy removal, computation of Chebyshev centers and solving linear feasibility problems. Funding Agencies|Swedish Research Council (VR)Swedish Research Council [2017-04710]

Background In the comparative genomics field, one of the goals is to estimate a sequence of genetic changes capable of transforming a genome into another. Genome rearrangement events are mutations that can alter the genetic content or the arrangement of elements from the genome. Reversal and transposition are two of the most studied genome rearrangement events. A reversal inverts a segment of a genome while a transposition swaps two consecutive segments. Initial studies in the area considered only the order of the genes. Recent works have incorporated other genetic information in the model. In particular, the information regarding the size of intergenic regions, which are structures between each pair of genes and in the extremities of a linear genome. Results and conclusions In this work, we investigate the sorting by intergenic reversals and transpositions problem on genomes sharing the same set of genes, considering the cases where the orientation of genes is known and unknown. Besides, we explored a variant of the problem, which generalizes the transposition event. As a result, we present an approximation algorithm that guarantees an approximation factor of 4 for both cases considering the reversal and transposition (classic definition) events, an improvement from the 4.5-approximation previously known for the scenario where the orientation of the genes is unknown. We also present a 3-approximation algorithm by incorporating the generalized transposition event, and we propose a greedy strategy to improve the performance of the algorithms. We performed practical tests adopting simulated data which indicated that the algorithms, in both cases, tend to perform better when compared with the best-known algorithms for the problem. Lastly, we conducted experiments using real genomes to demonstrate the applicability of the algorithms.

We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additionally, we introduce a new multi-factor notion of approximation that is specifically tailored to the multiobjective case and its inherent trade-offs between different objectives. For minimization problems, we provide an efficient algorithm that computes an approximation of a multiobjective problem by using an exact or approximate algorithm for its weighted sum scalarization. In case that an exact algorithm for the weighted sum scalarization is used, this algorithm comes arbitrarily close to the best approximation quality that is obtainable by supported solutions – both with respect to the common notion of approximation and with respect to the new multi-factor notion. Moreover, the algorithm yields the currently best approximation results for several well-known multiobjective minimization problems. For maximization problems, however, we show that a polynomial approximation guarantee can, in general, not be obtained in more than one of the objective functions simultaneously by supported solutions.

Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α-ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 120 degrees (however, our approximation ratios hold for any α ⩾ 120 degrees). 1) The α-minimum spanning tree problem asks for an α-ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α-ST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. 2) To examine what is possible with non-uniform wedge angles, we define an ̅α-ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α. We present an algorithm to find an ̅α-ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α. Our algorithm runs in linear time after computing the MST., LIPIcs, Vol. 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), pages 14:1-14:22

We consider the stochastic generalized Nash equilibrium problem (SGNEP) with expected-value cost functions. Inspired by Yi and Pavel (2019), we propose a distributed generalized Nash equilibrium seeking algorithm based on the preconditioned forward-backward operator splitting for SGNEPs, where, at each iteration, the expected value of the pseudogradient is approximated via a number of random samples. Our main contribution is to show almost sure convergence of the proposed algorithm if the pseudogradient mapping is restricted (monotone and) cocoercive.

The objective of this note is to introduce a novel data-driven iterative linear quadratic control method for solving a class of nonlinear optimal tracking problems. Specifically, an algorithm is proposed to approximate the Q-factors arising from linear quadratic stochastic optimal tracking problems. This algorithm is then coupled with iterative linear quadratic methods for determining local solutions to nonlinear optimal tracking problems in a purely data-driven setting. Simulation results highlight the potential of this method for field applications.

We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an n-vertex graph G and an integer k, constructs a tree-partition of width O(k7) for G or reports that G has tree-partition width more than k, in time kO(1)n2. We can improve slightly on the approximation factor by sacrificing the dependence on k, or on n. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is W[t]-hard for all t. We deduce XALP-completeness of the problem of computing the domino treewidth. Finally, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width.

We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an n-vertex graph G and an integer k, constructs a tree-partition of width O(k⁷) for G or reports that G has tree-partition width more than k, in time k^O(1) n². We can improve slightly on the approximation factor by sacrificing the dependence on k, or on n. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is W[t]-hard for all t. We deduce XALP-completeness of the problem of computing the domino treewidth. Finally, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width., LIPIcs, Vol. 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), pages 7:1-7:20

International audience; In this work, we consider the problem of pattern matching under the dynamic time warping (DTW) distance motivated by potential applications in the analysis of biological data produced by the third generation sequencing. To measure the DTW distance between two strings, one must "warp" them, that is, double some letters in the strings to obtain two equal-lengths strings, and then sum the distances between the letters in the corresponding positions. When the distances between letters are integers, we show that for a pattern P with m runs and a text T with n runs: 1. There is an O(m + n)-time algorithm that computes all locations where the DTW distance from P to T is at most 1; 2. There is an O(kmn)-time algorithm that computes all locations where the DTW distance from P to T is at most k. As a corollary of the second result, we also derive an approximation algorithm for general metrics on the alphabet.

We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an $O(1)$-approximation in sublinear update time for set cover for axis-aligned squares in 2D. More precisely, we obtain randomized update time $O(n^{2/3+\delta})$ for an arbitrarily small constant $\delta>0$. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D. As a byproduct, our techniques for dynamic set cover also yield an optimal randomized $O(n\log n)$-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier $O(n\log n(\log\log n)^{O(1)})$ result [SoCG 2020]., Journal of Computational Geometry, Vol. 13 No. 2: Special Issue of Selected Papers from SoCG 2021

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an O(1)-approximation algorithm for the disjoint connected k-center and k-diameter problem for Euclidean spaces of low dimension (constant d) and for metrics with constant doubling dimension. For general metrics, we get an O(log²k)-approximation. Our algorithms work by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 50:1-50:20

The mathematical foundation of deep learning is the theorem that any continuous function can be approximated within any specified accuracy by using a neural network with certain non-linear activation functions. However, this theorem does not tell us what the network architecture should be and what the values of the weights are. One must train the network to estimate the weights. There is no guarantee that the optimal weights can be reached after training. This paper develops an explicit architecture of a universal deep network by using the Gray code order and develops an explicit formula for the weights of this deep network. This architecture is target function independent. Once the target function is known, the weights are calculated by the proposed formula, and no training is required. There is no concern whether the training may or may not reach the optimal weights. This deep network gives the same result as the shallow piecewise linear interpolation function for an arbitrary target function.

Utility companies collect usage data from meters on a regular basis. The usage data are collected automatically using radio-frequency identification (RFID) technology. Each meter transmits signals from an RFID tag that are read by a vehicle-mounted reading device within a specified distance. Routing the vehicles can be modeled by a close-enough vehicle routing problem on a street network. In practice, there is uncertainty while reading meters. The signal transmitted by an RFID tag is discontinuous, and the range that each meter can be read is different and stochastic due to weather conditions, surrounding obstacles, interference, and decreasing battery life of the RFID tags. These factors can lead to meters not being read. A vehicle has to be sent at a later time to read the missed meters, and this leads to increased costs for a utility company due to additional operational costs and overtime payments to drivers. Our aim is to address the uncertainty issues of the RFID technology by generating routes that are both cost-effective and robust (we seek to minimize the number of missed reads). We use data analytics, optimization, and Bayesian statistical models to address the uncertainty. Simulation experiments using real data show that the hierarchical Bayesian statistical model gives better results compared to other Bayesian statistical models. Utility companies can potentially integrate the results from the hierarchical Bayesian statistical model into their route generating software as a decision-support tool to produce routes that are more cost-effective and robust than the routes that they currently generate.

Predmet raziskovanja tega magistrskega dela je problem zapiranja centrov, ki spada med probleme razmeščanja ponudnikov. Predstavljene so osnovne lastnosti ter natančni algoritmi za reševanje problema. Zaradi NP-polnosti so predstavljeni tudi aproksimacijski algoritmi. Empirični testi na različnih omrežjih preverjajo časovno zahtevnost in kakovost rešitev aproksimacijskih algoritmov. Razmerje teh dveh lastnosti je prav tako primerjano. V namen testiranja algoritmov je razvito tudi poštno omrežje Slovenije, cilj katerega je reševanje problema zapiranja poštnih poslovalnic. The main topic of this thesis is the center closing problem, which is a facility location problem. Basic properties and exact algorithms for solving the problem are presented. Because the problem is NP-complete, approximation algorithms are also presented. Time complexity, the quality of results, and the ratio between the two are tested for approximation algorithms using empirical tests. For the purpose of testing the algorithms a postal network of Slovenia was constructed, the goal of which was to solve the post office closing problem.

The number of offspring and the population size greatly influence the performance of the Plant Propagation Algorithm, a crossover-less metaheuristic, when applied to the Euclidean traveling salesman problem. However, with large volumes of experimental data, a clearly characterizable relation emerges, facilitating both an exact parameterization as well as opening up perspectives on a precisely predictable outcome. These results directly question its position between exact, approximation, and PTAS algorithms. Although the metaheuristic is thereby officially parameter sensitive when deployed to the Euclidean traveling salesman problem, it does appear to be largely insensitive to different problem instances. This is very different from earlier results on continuous optimization, which were completely opposite. Why is that, and what does it mean for our practices in algorithmic benchmarking?

In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the "uniform case" of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mn k) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n²) can be obtained, but with a higher approximation guarantee of (2k-1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1+ε)-approximates the optimal fractional solution in Õ(m/ε²) time (independent of k), which can be turned into a (2+ε) approximation algorithm that runs in time Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 37:1-37:20

We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a $k$-edge-connected graph $G=(V,E)$ and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to $G$ makes the graph $(k+1)$-edge-connected. If $k$ is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP) -- i.e., $G$ is a spanning tree -- for which significant progress has been achieved recently, leading to approximation factors below $1.5$ (the currently best factor is $1.458$). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below $2$ for CAP by presenting a $1.91$-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below $1.5$, based on a new analysis technique. Through these ingredients, we obtain a $1.393$-approximation algorithm for CAP, and therefore also TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned $1.91$-approximation for CAP and also the previously best approximation factor of $1.458$ for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below $1.5$.

A directed graph $G=(V,E)$ is strongly biconnected if $G$ is strongly connected and its underlying graph is biconnected. A strongly biconnected directed graph $G=(V,E)$ is called $2$-vertex-strongly biconnected if $|V|\geq 3$ and the induced subgraph on $V\setminus\left\lbrace w\right\rbrace $ is strongly biconnected for every vertex $w\in V$. In this paper we study the following problem. Given a $2$-vertex-strongly biconnected directed graph $G=(V,E)$, compute an edge subset $E^{2sb} \subseteq E$ of minimum size such that the subgraph $(V,E^{2sb})$ is $2$-vertex-strongly biconnected.

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that ``polynomial-time'' means ``efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

We describe a simple deterministic O(e-1 log A) round distributed algorithm for (2a + 1)(1 + e) approximation of minimum weighted dominating set on graphs with arboricity at most a. Here A denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O(a(2)) approximation in O(log n) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic O(a log ?) approximation in O(log A) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic O(a) approximation in O(log(2)?) rounds (implicit in Bansal et al. in Inform Process Lett 122:21-24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized O(a) approximation in O(a log n) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized O(a log ?) round distributed algorithm that sharpens the approximation factor to a (1 + o(1)). If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve a - 1 - e approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017)., Distributed Computing, ISSN:0178-2770, ISSN:1432-0452

The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a 2-approximation for a wide class of these problems. However nothing better is known even for very basic special cases, raising the natural question whether any improved approximation factor is possible at all. In this paper we address one of the most basic problems in this family for which 2 is still the best-known approximation factor, the Forest Augmentation Problem (FAP): given an undirected unweighted graph (that w.l.o.g. we can assume to be a forest) and a collection of extra edges (links), compute a minimum cardinality subset of links whose addition to the graph makes it 2-edge-connected. Several better-than-2 approximation algorithms are known for the special case where the input graph is a tree, a.k.a. the Tree Augmentation Problem (TAP), see e.g. [Grandoni, Kalaitzis, Zenklusen-STOC'18; Cecchetto, Traub, Zenklusen-STOC'21] and references therein. Recently this was achieved also for the weighted version of TAP [Traub, Zenklusen-FOCS'21], and for the k-connectivity generalization of TAP [Byrka, Grandoni, Jabal-Ameli-STOC'20; Cecchetto, Traub, Zenklusen-STOC'21]. These results heavily exploit the fact that the input graph is connected, a condition that does not hold in FAP. In this paper we breach the 2-approximation barrier for FAP. Our result is based on two main ingredients. First, we describe a reduction to the Path Augmentation Problem (PAP), the special case of FAP where the input graph is a collection of disjoint paths. Our reduction is not approximation preserving, however it is sufficiently accurate to improve on a factor 2 approximation. Second, we present a better-than-2 approximation algorithm for PAP, an open problem on its own. Here we exploit a novel notion of implicit credits which might turn out to be helpful in future related work.

A quantitative description of the excited electronic states of point defects and impurities is crucial for understanding materials properties, and possible applications of defects in quantum technologies. This is a considerable challenge for computational methods, since Kohn-Sham density-functional theory (DFT) is inherently a ground state theory, while higher-level methods are often too computationally expensive for defect systems. Recently, embedding approaches have been applied that treat defect states with many-body methods, while using DFT to describe the bulk host material. We implement such an embedding method, based on Wannierization of defect orbitals and the constrained random-phase approximation approach, and perform systematic characterization of the method for three distinct systems with current technological relevance: a carbon dimer replacing a B and N pair in bulk hexagonal BN (C$_{\text{B}}$C$_{\text{N}}$), the negatively charged nitrogen-vacancy center in diamond (NV$^-$), and an Fe impurity on the Al site in wurtzite AlN ($\text{Fe}_{\text{Al}}$). For C$_{\text{B}}$C$_{\text{N}}$ we show that the embedding approach gives many-body states in agreement with analytical results on the Hubbard dimer model, which allows us to elucidate the effects of the DFT functional and double-counting correction. For the NV$^-$ center, our method demonstrates good quantitative agreement with experiments for the zero-phonon line of the triplet-triplet transition. Finally, we illustrate challenges associated with this method for determining the energies and orderings of the complex spin multiplets in $\text{Fe}_{\text{Al}}$., Comment: 19 pages, 14 figures. Supplemental material: 7 pages

In this paper, a parallel structured divide-and-conquer (PSDC) eigensolver is proposed for symmetric tridiagonal matrices based on ScaLAPACK and a parallel structured matrix multiplication algorithm, called PSMMA. Computing the eigenvectors via matrix-matrix multiplications is the most computationally expensive part of the divide-and-conquer algorithm, and one of the matrices involved in such multiplications is a rank-structured Cauchy-like matrix. By exploiting this particular property, PSMMA constructs the local matrices by using generators of Cauchy-like matrices without any communication, and further reduces the computation costs by using a structured low-rank approximation algorithm. Thus, both the communication and computation costs are reduced. Experimental results show that both PSMMA and PSDC are highly scalable and scale to 4096 processes at least. PSDC has better scalability than PHDC that was proposed in [J. Comput. Appl. Math. 344 (2018) 512--520] and only scaled to 300 processes for the same matrices. Comparing with \texttt{PDSTEDC} in ScaLAPACK, PSDC is always faster and achieves $1.4$x--$1.6$x speedup for some matrices with few deflations. PSDC is also comparable with ELPA, with PSDC being faster than ELPA when using few processes and a little slower when using many processes., 17 pages, 9 figures

Industry 4.0 utilizes the Internet of Things (IoT) to rise the efficiency in manufacturing and automation where wireless sensor networks (WSNs) are crucial technologies for communication layer of IoT. WSNs include hundreds of small sized sensor nodes that have the abilities of wireless transmission and environmental sensing. Wireless transmission is prone to various attacks such as data manipulation since data communication is achieved through transfer of radio packets. A countermeasure of this issue is link monitoring by deploying secure points that can physically capture and inspect radio packets. Graph theory plays a critical role to solve various problems in WSNs. Finding minimum Vertex Cover (VC) is an important NP-Hard graph theoretic problem in which the minimum set of nodes (vertices) is aimed to select in such a way that each link should be incident to at least one node from this set. VC is a significant structure for WSNs where it perfectly fits for link monitoring when nodes in VC are set as secure points (monitors). Since sensor nodes are generally battery-powered and have limited transmission range, energy-efficient multi-hop communication to the sink node is of utmost importance. In weighted connected VC (WCVC) structure, subgraph induced by monitor nodes are connected where monitors are chosen according to their weights. When weights of nodes are assigned as reciprocal of their energies, an energy-efficient virtual backbone can be formed. We propose a novel metaheuristic WCVC algorithm for link monitoring and backbone formation in WSNs modeled as undirected graphs. Our proposed algorithm integrates a genetic search with a greedy heuristic to improve WCVC solution quality and decrease the search time. To evaluate the efficiencies of greedy heuristics, we adopt three different heuristics for WCVC problem. We implement our algorithm with its counterparts and reveal that the algorithm is favorable in terms of solution quality and resource consumption.