NDLI: Discrete Optimization by Relational Constraint Satisfaction

Content Provider	IEEE Xplore Digital Library
Author	Ullmann, J. R.
Copyright Year	1979
Abstract	In pattern matching a basic problem is to determine one or more vectors X that maximize an objective function which is a sum of functions of components of X. When this problem is solved by dynamic programming CPU time and storage requirements grow explosively as the amount of intervariable interaction in the objective function increases. This explosion may be reduced by departing from the traditional dynamic programming method of eliminating successive variables and instead determining a constraint relation between each variable and all others with which it interacts. Discrete relaxation is used to accelerate a backtrack search to find all vectors that satisfy all such constraints. Optimization is achieved by evaluating the objective function for all such vectors. This new method of optimization has been experimentally compared with a classical dynamic programming algorithm running with the same pseudorandomly generated objective functions.
Sponsorship	IEEE Computer Society
Starting Page	544
Ending Page	551
Page Count	8
File Size	1410496
File Format	PDF
ISSN	01628828
Volume Number	PAMI-4
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1982-09-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Constraint optimization Dynamic programming Explosions Labeling Pattern matching Acceleration Optimization methods Computer science Heuristic algorithms Bibliographies pattern matching Consistent labeling constraint satisfaction discrete optimization discrete relaxation dynamic programming
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence Computational Theory and Mathematics Computer Vision and Pattern Recognition Software

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

A Gradient Projection Algorithm for Relaxation Methods

On-Line Video Event Detection by Constraint Flow

On the Foundations of Relaxation Labeling Processes

Relaxation Labeling with Learning Automata

Fast unambiguous stereo matching using reliability-based dynamic programming

The Consistent Labeling Problem: Part II

Localizing Overlapping Parts by Searching the Interpretation Tree

A Dynamic Programming Algorithm for the Distance Between Two Finite Areas

Dynamic Programming and Graph Algorithms in Computer Vision

Discrete Optimization by Relational Constraint Satisfaction

Similar Documents

A Gradient Projection Algorithm for Relaxation Methods

On-Line Video Event Detection by Constraint Flow

On the Foundations of Relaxation Labeling Processes

Relaxation Labeling with Learning Automata

Fast unambiguous stereo matching using reliability-based dynamic programming

The Consistent Labeling Problem: Part II

Localizing Overlapping Parts by Searching the Interpretation Tree

A Dynamic Programming Algorithm for the Distance Between Two Finite Areas

Dynamic Programming and Graph Algorithms in Computer Vision

Discrete Optimization by Relational Constraint Satisfaction