DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.75

Product-State Approximation Algorithms for the Transverse Field Ising Model

Authors: Vincenzo Lipardi, David Mestel, and Georgios Stamoulis

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We study classical polynomial-time approximation algorithms for the transverse field Ising model (TFIM), allowing a mixture of ferromagnetic and antiferromagnetic interactions between pairs of qubits, alongside transverse field terms with arbitrary non-negative weights. In this work, we first prove a second-order conic inequality based on the anticommutation property of the two competing terms (Ising Z_i Z_j vs. field X_i terms), and we use this inequality to strengthen the basic SDP relaxation of the problem. By producing two competing rounded product state solutions and taking the better of the two we achieve an approximation ratio γ≈ 0.7860. A further improvement by non-uniform interpolation achieves a ratio γ ≈ 0.82197. Finally, we give an explicit purely antiferromagnetic TFIM instance on three qubits for which every product state achieves at most 169/180≈ 0.9389 of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely antiferromagnetic case.

Cite as

Vincenzo Lipardi, David Mestel, and Georgios Stamoulis. Product-State Approximation Algorithms for the Transverse Field Ising Model. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lipardi_et_al:LIPIcs.MFCS.2026.75,
  author =	{Lipardi, Vincenzo and Mestel, David and Stamoulis, Georgios},
  title =	{{Product-State Approximation Algorithms for the Transverse Field Ising Model}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.75},
  URN =		{urn:nbn:de:0030-drops-274574},
  doi =		{10.4230/LIPIcs.MFCS.2026.75},
  annote =	{Keywords: Ising model, Hamiltonian Complexity, Approximation Algorithms, Semidefinite Programming}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2013.461

PTAS for Ordered Instances of Resource Allocation Problems

Authors: Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract

We consider the problem of fair allocation of indivisible goods where we are given a set I of m indivisible resources (items) and a set P of n customers (players) competing for the resources. Each resource j in I has a same value vj > 0 for a subset of customers interested in j and it has no value for other customers. The goal is to find a feasible allocation of the resources to the interested customers such that in the Max-Min scenario (also known as Santa Claus problem) the minimum utility (sum of the resources) received by each of the customers is as high as possible and in the Min-Max case (also known as R||C_max problem), the maximum utility is as low as possible. In this paper we are interested in instances of the problem that admit a PTAS. These instances are not only of theoretical interest but also have practical applications. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a convex bipartite graph; there exists an ordering of the resources such that each customer is interested (has positive evaluation) in a set of consecutive resources and we demonstrate a PTAS. For the Min-Max allocation problem, we obtain a PTAS for instances in which there is an ordering of the customers (machines) and each resource (job) is adjacent to a consecutive set of customers (machines). Next we show that our method for the Max-Min scenario, can be extended to a broader class of bipartite graphs where the resources can be viewed as a tree and each customer is interested in a sub-tree of a bounded number of leaves of this tree (e.g. a sub-path).

Cite as

Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis. PTAS for Ordered Instances of Resource Allocation Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 461-473, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{khodamoradi_et_al:LIPIcs.FSTTCS.2013.461,
  author =	{Khodamoradi, Kamyar and Krishnamurti, Ramesh and Rafiey, Arash and Stamoulis, Georgios},
  title =	{{PTAS for Ordered Instances of Resource Allocation Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{461--473},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.461},
  URN =		{urn:nbn:de:0030-drops-43936},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.461},
  annote =	{Keywords: Approximation Algorithms, Convex Bipartite Graphs, Resource Allocation}
}

Search Results

Documents authored by Stamoulis, Georgios

Product-State Approximation Algorithms for the Transverse Field Ising Model

Abstract

Cite as

PTAS for Ordered Instances of Resource Allocation Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message