Approximating Steiner trees and forests with minimum number of Steiner points

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Cyclic Queuing and Forwarding (CQF) is a mechanism defined by IEEE TSN for providing low jitter in a deterministic network. CQF uses a common time cycle and two buffers per node output port: during one cycle incoming packets are stored in one buffer while ...

Region extraction is a very common task in both Computer Science and Engineering with several applications in object recognition and motion analysis, among others. Most of the literature focuses on regions delimited by straight lines, often in the special ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

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 ...

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

Objective. Powered lower-limb prostheses relying on decoding motor intentions from non-invasive sensors, like electromyographic (EMG) signals, can significantly improve the quality of life of amputee subjects. However, the optimal combination of high decod ...

The popular isolation level multiversion Read Committed (RC) exchanges some of the strong guarantees of serializability for increased transaction throughput. Nevertheless, transaction workloads can sometimes be executed under RC while still guaranteeing se ...

Universal cross-site scripting (UXSS) is a browser vulnerability, making a vulnerable browser execute an attacker's script on any web pages loaded by the browser. UXSS is considered a far more severe vulnerability than well-studied cross-site scripting (XS ...

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

Unrefinement is a tool that allows to perform faster numerical simulations by controlling the level of precision in the specified area. We introduce an algorithm that creates a coarser geometry from an initial regular geometry, which is represented with re ...

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

The currently ongoing NIST LWC project aims at identifying new standardization targets for lightweight authenticated encryption with associated data (AEAD) and (optionally) lightweight cryptographic hashing. NIST has deemed it important for performance and ...

With the current exponential growth of video-based social networks, video retrieval using natural language is receiving ever-increasing attention. Most existing approaches tackle this task by extracting individual frame-level spatial features to represent ...

We study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimina ...

Approximating Steiner trees and forests with minimum number of Steiner points

Chat with Graph Search

Configuration of Guard Band and Offsets in Cyclic Queuing and Forwarding

Region Extraction in Mesh Intersection

Results on Sparse Integer Programming and Geometric Independent Sets

Fairness and Explainability in Clustering Problems

Approximation Algorithms for Allocation and Network Design

Maximum Independent Set: Self-Training through Dynamic Programming

Early decoding of walking tasks with minimal set of EMG channels

When is it safe to run a transactional workload under Read Committed?

FUZZORIGIN: Detecting UXSS vulnerabilities in Browsers through Origin Fuzzing

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

An unrefinement algorithm for planar THB-spline parameterizations

Spectral Hypergraph Sparsifiers of Nearly Linear Size

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Power Yoga: Variable-Stretch Security of CCM for Energy-Efficient Lightweight IoT

Semantics-Aware Spatial-Temporal Binaries for Cross-Modal Video Retrieval

The (h, k)-Server Problem on Bounded Depth Trees

Local Approximation of the Maximum Cut in Regular Graphs

Fair colorful k-center clustering

Computation Of A 30750-Bit Binary Field Discrete Logarithm