Search results for "MaxCut"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
99	Philip N. Klein, Hsueh-I Lu	Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs.	ISAAC	1998	DBLP DOI BibTeX RDF
99	Jun Dong Cho, Salil Raje, Majid Sarrafzadeh	Approximation Algorithm on Multi-Way Maxcut Partitioning.	ESA	1994	DBLP DOI BibTeX RDF
62	Garud Iyengar, David J. Phillips, Clifford Stein 0001	Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring.	IPCO	2005	DBLP DOI BibTeX RDF
62	Steven Homer, Marcus Peinado	A highly parallel algorithm to approximate MaxCut on distributed memory architectures.	IPPS	1995	DBLP DOI BibTeX RDF	MaxCut, maximum weight cut, weighted undirected graph, linear speedup, parallel algorithms, parallel algorithm, graph theory, distributed memory systems, distributed memory architectures, Connection Machine
55	Alberto Bertoni, Paola Campadelli, Roberto Posenato	An Upper Bound for the Maximum Cut Mean Value.	WG	1997	DBLP DOI BibTeX RDF
44	Wenceslas Fernandez de la Vega, Claire Kenyon-Mathieu	Linear programming relaxations of maxcut.	SODA	2007	DBLP BibTeX RDF
44	Andreas Björklund	Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs.	ESA	2005	DBLP DOI BibTeX RDF
44	Thomas Hofmeister, Hanno Lefmann	A Combinatorial Design Approach to MAXCUT.	STACS	1996	DBLP DOI BibTeX RDF
37	Subhash Khot, Ryan O'Donnell	SDP gaps and UGC-hardness for MAXCUTGAIN.	FOCS	2006	DBLP DOI BibTeX RDF
26	Vorapong Suppakitpaisarn, Jin-Kao Hao	Utilizing Graph Sparsification for Pre-processing in Maxcut QUBO Solver.	CoRR	2024	DBLP DOI BibTeX RDF
26	Reuben Tate, Stephan J. Eidenbenz	Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits.	CoRR	2024	DBLP DOI BibTeX RDF
26	Daniel Rehfeldt, Thorsten Koch, Yuji Shinano	Faster exact solution of sparse MaxCut and QUBO problems.	Math. Program. Comput.	2023	DBLP DOI BibTeX RDF
26	Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble	Solving MaxCut with quantum imaginary time evolution.	Quantum Inf. Process.	2023	DBLP DOI BibTeX RDF
26	Celina M. H. de Figueiredo, Alexsander Andrade de Melo, Fabiano de S. Oliveira, Ana Silva 0001	MaxCut on permutation graphs is NP-complete.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
26	Ivan Bliznets, Vladislav Epifanov	MaxCut Above Guarantee.	MFCS	2023	DBLP DOI BibTeX RDF
26	Bradley H. Theilman, Yipu Wang, Ojas Parekh, William Severa, J. Darby Smith, James B. Aimone	Stochastic Neuromorphic Circuits for Solving MAXCUT.	IPDPS	2023	DBLP DOI BibTeX RDF
26	Bradley H. Theilman, James B. Aimone	Goemans-Williamson MAXCUT approximation algorithm on Loihi.	NICE	2023	DBLP DOI BibTeX RDF
26	Daniel Rehfeldt, Thorsten Koch, Yuji Shinano	Faster exact solution of sparse MaxCut and QUBO problems.	CoRR	2022	DBLP BibTeX RDF
26	Celina M. H. de Figueiredo, Alexsander Andrade de Melo, Fabiano de S. Oliveira, Ana Silva 0001	MaxCut on Permutation Graphs is NP-complete.	CoRR	2022	DBLP BibTeX RDF
26	Bradley H. Theilman, Yipu Wang, Ojas D. Parekh, William Severa, J. Darby Smith, James B. Aimone	Stochastic Neuromorphic Circuits for Solving MAXCUT.	CoRR	2022	DBLP DOI BibTeX RDF
26	Lis Arufe, Miguel A. González 0001, Angelo Oddi, Riccardo Rasconi, Ramiro Varela	Quantum circuit compilation by genetic algorithm for quantum approximate optimization algorithm applied to MaxCut problem.	Swarm Evol. Comput.	2022	DBLP DOI BibTeX RDF
26	Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, Leo Zhou	The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model.	TQC	2022	DBLP DOI BibTeX RDF
26	Jessica K. Thompson, Ojas Parekh, Kunal Marwaha	An explicit vector algorithm for high-girth MaxCut.	SOSA	2022	DBLP DOI BibTeX RDF
26	Jan Kratochvíl, Tomás Masarík, Jana Novotná 0001	U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited.	Algorithmica	2021	DBLP DOI BibTeX RDF
26	Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, Leo Zhou	The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model.	CoRR	2021	DBLP BibTeX RDF
26	Stefan Steinerberger	A 0.502·MaxCut Approximation using Quadratic Programming.	CoRR	2021	DBLP BibTeX RDF
26	Jessica K. Thompson, Ojas Parekh, Kunal Marwaha	An explicit vector algorithm for high-girth MaxCut.	CoRR	2021	DBLP BibTeX RDF
26	Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble, George Siopsis	Impact of graph structures for QAOA on MaxCut.	Quantum Inf. Process.	2021	DBLP DOI BibTeX RDF
26	Jan Kratochvíl, Tomás Masarík, Jana Novotná 0001	U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited.	CoRR	2020	DBLP BibTeX RDF
26	Jan Kratochvíl, Tomás Masarík, Jana Novotná 0001	U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited.	MFCS	2020	DBLP DOI BibTeX RDF
26	Marcel Kenji de Carli Silva, Levent Tunçel	Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP.	SIAM J. Optim.	2019	DBLP DOI BibTeX RDF
26	Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian	Sublinear Algorithms for MAXCUT and Correlation Clustering.	CoRR	2018	DBLP BibTeX RDF
26	Lior Gishboliner, Michael Krivelevich, Gal Kronenberg	On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments.	Random Struct. Algorithms	2018	DBLP DOI BibTeX RDF
26	Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian	Sublinear Algorithms for MAXCUT and Correlation Clustering.	ICALP	2018	DBLP DOI BibTeX RDF
26	Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto Imbuzeiro Oliveira	Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality.	COLT	2017	DBLP BibTeX RDF
26	Sostenes L. Lins, Diogo B. Henriques	An O(\|E\|)-linear Model for the MaxCut Problem.	CoRR	2016	DBLP BibTeX RDF
26	Lior Gishboliner, Michael Krivelevich, Gal Kronenberg	On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments.	CoRR	2016	DBLP BibTeX RDF
26	Yatao Bian, Alexey Gronskiy, Joachim M. Buhmann	Greedy MAXCUT Algorithms and their Information Content.	CoRR	2016	DBLP BibTeX RDF
26	Yatao Bian, Alexey Gronskiy, Joachim M. Buhmann	Information-theoretic analysis of MaxCut algorithms.	ITA	2016	DBLP DOI BibTeX RDF
26	Irène Waldspurger, Alexandre d'Aspremont, Stéphane Mallat	Phase recovery, MaxCut and complex semidefinite programming.	Math. Program.	2015	DBLP DOI BibTeX RDF
26	Yatao Bian, Alexey Gronskiy, Joachim M. Buhmann	Greedy MaxCut algorithms and their information content.	ITW	2015	DBLP DOI BibTeX RDF
26	Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks	On the practically interesting instances of MAXCUT.	STACS	2013	DBLP DOI BibTeX RDF
26	Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks	On the practically interesting instances of MAXCUT	CoRR	2012	DBLP BibTeX RDF
26	Xiaojun Zhou	Improved Canonical Dual Algorithms for the Maxcut Problem	CoRR	2012	DBLP BibTeX RDF
26	M. Shel Swenson, Rahul Suri, C. Randal Linder, Tandy J. Warnow	An experimental study of Quartets MaxCut and other supertree methods.	Algorithms Mol. Biol.	2011	DBLP DOI BibTeX RDF
26	Luigi Grippo, Laura Palagi, Veronica Piccialli	An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem.	Math. Program.	2011	DBLP DOI BibTeX RDF
26	Satyen Kale, C. Seshadhri 0001	Combinatorial Approximation Algorithms for MaxCut using Random Walks.	ICS	2011	DBLP BibTeX RDF
26	Sagi Snir, Satish Rao	Quartets MaxCut: A Divide and Conquer Quartets Algorithm.	IEEE ACM Trans. Comput. Biol. Bioinform.	2010	DBLP DOI BibTeX RDF
26	Satyen Kale, C. Seshadhri 0001	Combinatorial Approximation Algorithms for MaxCut using Random Walks	CoRR	2010	DBLP BibTeX RDF
26	M. Shel Swenson, Rahul Suri, C. Randal Linder, Tandy J. Warnow	An Experimental Study of Quartets MaxCut and Other Supertree Methods.	WABI	2010	DBLP DOI BibTeX RDF
26	Venkatesh Raman 0001, Saket Saurabh 0001	Improved fixed parameter tractable algorithms for two "edge" problems: MAXCUT and MAXDAG.	Inf. Process. Lett.	2007	DBLP DOI BibTeX RDF
26	Artur Czumaj, Gereon Frahling, Christian Sohler	Efficient Kinetic Data Structures for MaxCut.	CCCG	2007	DBLP BibTeX RDF
26	Kartik Krishnan, John E. Mitchell 0001	A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem.	Comput. Optim. Appl.	2006	DBLP DOI BibTeX RDF
26	Enrique Mérida Casermeiro, Domingo López-Rodríguez, Juan Miguel Ortiz-de-Lazcano-Lobato	Enhanced maxcut clustering with multivalued neural networks and functional annealing.	ESANN	2006	DBLP BibTeX RDF
26	Meena Mahajan, Venkatesh Raman 0001	Parameterizing above Guaranteed Values: MaxSat and MaxCut.	J. Algorithms	1999	DBLP DOI BibTeX RDF
26	Jun Dong Cho, Salil Raje, Majid Sarrafzadeh	Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering vor VLSI Applications.	IEEE Trans. Computers	1998	DBLP DOI BibTeX RDF
26	Steven Homer, Marcus Peinado	Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut.	J. Parallel Distributed Comput.	1997	DBLP DOI BibTeX RDF
26	Meena Mahajan, Venkatesh Raman 0001	Parametrizing Above Guaranteed Values: MaxSat and MaxCut	Electron. Colloquium Comput. Complex.	1997	DBLP BibTeX RDF
26	Thomas Hofmeister, Hanno Lefmann	A combinatorial design approach to MAXCUT.	Random Struct. Algorithms	1996	DBLP DOI BibTeX RDF
18	Joel A. Tropp	Column subset selection, matrix factorization, and eigenvalue optimization.	SODA	2009	DBLP DOI BibTeX RDF
18	Claire Mathieu, Warren Schudy	Yet another algorithm for dense max cut: go greedy.	SODA	2008	DBLP BibTeX RDF
18	Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, Alexander Wolff 0001	Drawing (Complete) Binary Tanglegrams.	GD	2008	DBLP DOI BibTeX RDF
18	Prasad Raghavendra	Optimal algorithms and inapproximability results for every CSP?	STOC	2008	DBLP DOI BibTeX RDF	dictatorship tests, rounding schemes, semidefinite programming, constraint satisfaction problem, unique games conjecture
18	Michael Krüger, Harald Hempel	Approximating Alternative Solutions.	COCOON	2008	DBLP DOI BibTeX RDF
18	Zhaosong Lu, Arkadi Nemirovski, Renato D. C. Monteiro	Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm.	Math. Program.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C22, 90C25, 90C51, 65K10
18	Christian Borgs, Jennifer T. Chayes, László Lovász 0001, Vera T. Sós, Balázs Szegedy, Katalin Vesztergombi	Graph limits and parameter testing.	STOC	2006	DBLP DOI BibTeX RDF	convergence of graphs, distance of graphs, graph limit, property testing, graph homomorphism
18	Michael Langberg, Yuval Rabani, Chaitanya Swamy	Approximation Algorithms for Graph Homomorphism Problems.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
18	Enrique Mérida Casermeiro, Domingo López-Rodríguez	Graph Partitioning via Recurrent Multivalued Neural Networks.	IWANN	2005	DBLP DOI BibTeX RDF
18	Moses Charikar, Anthony Wirth	Maximizing Quadratic Programs: Extending Grothendieck's Inequality.	FOCS	2004	DBLP DOI BibTeX RDF
18	Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell	Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?	FOCS	2004	DBLP DOI BibTeX RDF
18	Philipp Woelfel	A Construction Method for Optimally Universal Hash Families and Its Consequences for the Existence of RBIBDs.	COCOON	2004	DBLP DOI BibTeX RDF
18	Stefan A. Blum	From a CORBA-Based Software Framework to a Component-Based System Architecture for Controlling a Mobile Robot.	ICVS	2003	DBLP DOI BibTeX RDF
18	Martin Skutella	Convex quadratic and semidefinite programming relaxations in scheduling.	J. ACM	2001	DBLP DOI BibTeX RDF	unrelated machines, approximation algorithms, randomized algorithms, convex optimization, performance guarantee, scheduling theory, worst-case ratio
18	Garud Iyengar, Mehmet Tolga Çezik	Cutting Planes for Mixed 0-1 Semidefinite Programs.	IPCO	2001	DBLP DOI BibTeX RDF
18	Martin Skutella	Semidefinite Relaxations for Parallel Machine Scheduling.	FOCS	1998	DBLP DOI BibTeX RDF	scheduling, approximation algorithms, randomized algorithms, semidefinite programming, convex programming
18	Katja Wolf	Dense Instances of Hard Optimization Problems.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
18	Thomas Hofmeister, Martin Hühne	Semidefinite Programming and Its Applications to Approximation Algorithms.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
18	Yoji Kajitani, Jun Dong Cho, Majid Sarrafzadeh	New Approximation Results on Graph Matching and related Problems.	WG	1994	DBLP DOI BibTeX RDF
18	Hans L. Bodlaender, Klaus Jansen	On the Complexity of the Maximum Cut Problem.	STACS	1994	DBLP DOI BibTeX RDF
18	Jun Dong Cho, Majid Sarrafzadeh, Mysore Sriram, Sung-Mo Kang	High-Performance MCM Routing.	IEEE Des. Test Comput.	1993	DBLP DOI BibTeX RDF