NDLI: Approximation algorithms for MAX RES CUT with limited unbalanced constraints

Content Provider	Springer Nature Link
Author	Ling, Aifan Tang, Le Xu, Chengxian
Copyright Year	2009
Abstract	Two kinds of MAX RES CUT problems, the MAX s−t CUT and the MAX s−t−v CUT, with limited unbalanced constraints are considered. Approximation algorithms used in Frieze and Jerrum (Integer Programming and Combinatorial Optimization, vol. 920, pp. 1–13, Springer, Berlin, 1995), Galbiati and Maffioli (Theor. Comput. Sci. 385:78–87, 2007), Han et al. (Math. Program. Ser. B 92:509–535, 2002) and Ye (Math. Programm. 90:101–111, 2001) are extended to the two MAX RES CUT problems. A special matrix P is constructed by which it can ensure that the given nodes s,t are feasible to equality constraints with probability one for the MAX s−t CUT and s,t,v are feasible to equality constraints with at least probability 0.912 for the MAX s−t−v CUT. A fussy greedy sizing-adjusted procedure is then proposed to confirm that the round solution is feasible for all constraints. We find these extensions are nontrivial and some interesting results about performance ratio are obtained for the MAX RES CUT problem with limited unbalanced constraints.
Starting Page	357
Ending Page	374
Page Count	18
File Format	PDF
ISSN	15985865
Journal	Journal of Applied Mathematics and Computing
Volume Number	33
Issue Number	1-2
e-ISSN	18652085
Language	English
Publisher	Springer-Verlag
Publisher Date	2009-05-15
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	MAX RES CUT Limited unbalanced constraints Approximation algorithm Semidefinite programming relaxation Large-scale problems Combinatorial optimization Programming involving graphs or networks Approximation methods and heuristics Mathematics of Computing Theory of Computation ApplicationMathematics/Computational Methods of Engineering Computational Mathematics and Numerical Analysis
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

Douglas–Rachford splitting method for semidefinite programming

Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs

Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms

Inverse minimum flow problem

(Robust) Edge-based semidefinite programming relaxation of sensor network localization

The heterochromatic cycles in edge-colored graphs

A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

Approximation algorithms for MAX RES CUT with limited unbalanced constraints

Similar Documents

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

Douglas–Rachford splitting method for semidefinite programming

Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs

Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms

Inverse minimum flow problem

(Robust) Edge-based semidefinite programming relaxation of sensor network localization

The heterochromatic cycles in edge-colored graphs

A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

Approximation algorithms for MAX RES CUT with limited unbalanced constraints