Concept

Maximum cut

Related publications (15)

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...

EPFL2020

Reduction of the sign problem near T=0 in quantum Monte Carlo simulations

Frédéric Mila, Jonathan D'Emidio

Building on a recent investigation of the Shastry-Sutherland model [S. Wessel et al., Phys. Rev. B 98, 174432 (2018)], we develop a general strategy to eliminate the Monte Carlo sign problem near the zero-temperature limit in frustrated quantum spin models ...

AMER PHYSICAL SOC2020

Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

Daniel Kuhn, Napat Rujeerapaiboon, Kilian Schindler, Wolfram Wiesemann

Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to ...

2019

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

Ola Nils Anders Svensson, Abbas Bazzi

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

INFORMS2019

Inversion Minimization in Majority-Inverter Graphs

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Eleonora Testa

In this paper, we present new optimization techniques for the recently introduced Majority-Inverter Graph (MIG). Our optimizations exploit intrinsic algebraic properties of MIGs and aim at rewriting the complemented edges of the graph without changi ...

2016

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Nisheeth Vishnoi

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ1 with constant distortion. We show that for an arbitrarily small constant δ > 0, for all large enough n, there is an n-point negative ...

Association for Computing Machinery2015

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Cooperative Relaying at Finite SNR–-Role of Quantize-Map-and-Forward

Christina Fragouli, Ayan Sengupta, I-Hsiang Wang

Quantize-Map-and-Forward (QMF) relaying has been shown to achieve the optimal diversity-multiplexing trade-off (DMT) for arbitrary slow fading full-duplex networks as well as for the single-relay half-duplex network. A key reason for the DMT-optimality of ...

2013

Microsimulation Framework for Urban Price-Taker Markets

Bilal Farooq

In the context of integrated transportation and other urban engineering infrastructure systems, there are many examples of markets, where consumers exhibit price-taking behaviour. While this behaviour is ubiquitous, the underlying mechanism can be captured ...

2013

Polynomial Approximations for Continuous Linear Programs

Daniel Kuhn

Continuous linear programs have attracted considerable interest due to their potential for modeling manufacturing, scheduling, and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude ...

2012

Graph Chatbot

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.