On some problems related to 2-level polytopes

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

In 1975, Erdős asked for the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turán-type results can be used to prove an upper bound of n3/2+o(1). However, this ...

The unifying theme of this thesis are decision trees. Given a boolean function

f

and an input

x

, a decision tree computes the value

f(x)

by repeatedly querying bits of

x

. Our work is two-fold. On one hand, we investigate direct sums and other relat ...

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

The sum-of-squares (SOS) approximation method is a technique used in optimization problems to derive lower bounds on the optimal value of an objective function. By representing the objective function as a sum of squares in a feature space, the SOS method t ...

We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...

In this paper, we propose an analytical stochastic dynamic programming (SDP) algorithm to address the optimal management problem of price-maker community energy storage. As a price-maker, energy storage smooths price differences, thus decreasing energy arb ...

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

How to measure students' Computational Problem-Solving (CPS) competencies is an ongoing research topic. Prevalent approaches vary by measurement tools (e.g., interactive programming, multiple-choice tests, or programming-independent tests) and task types ( ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Humans are chronically exposed to airborne microplastics (MPs) by inhalation. Various types of polymer particles have been detected in lung samples, which could pose a threat to human health. Inhalation toxicological studies are crucial for assessing the e ...

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...

The recent geopolitical conflicts in Europe have underscored the vulnerability of the current energy system to the volatility of energy carrier prices. In the prospect of defining robust energy systems ensuring sustainable energy supply in the future, the ...

Given two elliptic curves and the degree of an isogeny between them, finding the isogeny is believed to be a difficult problem—upon which rests the security of nearly any isogeny-based scheme. If, however, to the data above we add information about the beh ...

We propose an adaptive quantum algorithm to prepare accurate variational time evolved wave functions. The method is based on the projected variational quantum dynamics (pVQD) algorithm, that performs a global optimization with linear scaling in the number ...

The rapid development of wearable biomedical systems now enables real-time monitoring of electroencephalography (EEG) signals. Acquisition of these signals relies on electrodes. These systems must meet the design challenge of selecting an optimal set of el ...

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

Robots outside of the fenced factories have to deal with continuously changing environment, this requires fast and flexible modes of control. Planning methods or complex learning models can find optimal paths in complex surroundings, but they are computati ...

On some problems related to 2-level polytopes

Chattez avec Graph Search

Edge-disjoint cycles with the same vertex set

The Power of Decision Trees for Composition and Search Problems

A ride time-oriented scheduling algorithm for dial-a-ride problems

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Graph generative deep learning models with an application to circuit topologies

Theory and applications of the sum-of-squares technique

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Energy Management of Price-Maker Community Energy Storage by Stochastic Dynamic Programming

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

A Comparative Analysis of Tools & Task Types for Measuring Computational Problem-Solving

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Inhalation of Microplastics—A Toxicological Complexity

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Molecular hypergraph neural networks

Identification of typical district configurations: A two-step global sensitivity analysis framework

Isogeny Problems with Level Structure

Adaptive projected variational quantum dynamics

FETCH: A Fast and Efficient Technique for Channel Selection in EEG Wearable Systems

Efficient Continual Finite-Sum Minimization

Exact Obstacle Avoidance for Robots in Complex and Dynamic Environments Using Local Modulation