Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
EnglishSvenskaNorsk
Change search
ExportLink to record
Permanent link

Direct link
BETA

Project

Project type/Form of grant
Project grant
Title [sv]
Lexikografisk optimering för dataanalys på grafer
Title [en]
Lexicographic max-ordering optimization for data analysis on graphs
Abstract [sv]
Många grundläggande och svåra problem inom dataanalys och datavetenskap kan formuleras som optimeringsproblem. Det innebär att man för att lösa problemet först formulerar från ett kriterium – en optimeringsfunktion– som mäter hur bra varje möjlig lösning på problemet är. Därefter används olika optimeringsmetoder för att söka en lösning som är så bra som möjligt enligt det givna kriteriet. De optimeringsproblem som förekommer i praktiska dataanalystillämpningar är ofta svårlösta: lösningen kan bero av tusentals eller miljontals variabler, som samverkar med varandra på ett komplext sätt. Så kallade kombinatoriska optimeringsmetoder har dock visat sig vara väldigt framgångsrika för att lösa sådana problem. Ofta kan dessa metoder beräkna lösningar som är globalt optimala, d.v.s. lösningar som garanterat är minst lika bra som någon annan möjlig lösning enligt det givna kriteriet.I det här projektet studerar vi en särskild klass av optimeringsproblem, så kallade lexikografiska max-ordnings (Lex MO) problem. Vår forskning har visat att många intressanta optimeringsproblem, som är olösbara i sin ursprungliga form, blir lösbara om man formulerar om dem som Lex-MO problem. Projektet syftar till en detaljerad och systematisk karaktärisering av dessa Lex-MO problem. Vi frågar oss vilka av dessa problem som går att lösa, och vilka algoritmer som i så fall kan lösa dem effektivt. Projektet bidrar till en djupare teoretisk förståelse av denna viktiga klass av optimeringsproblem, och har också direkt inverkan inom många praktiska tillämpningar av dataanalys och datavetenskap.
Abstract [en]
Many problems in applied data- and computer science are naturally formulated as optimization problems. In this paradigm, we solve problems by first formulating a criterion that describes the qualities of a good solution. We then use various optimization methods to find a solution that is as good as possible according to our chosen criterion. The ubiquity of this approach to problem solving means that good optimization methods are a key enabling technology in many areas of computer science and its many applications. In this proposal, we focus on a special class of combinatorial optimization problems, called lexicographic max-ordering (Lex-MO) optimization problems. Our interest in this class of problems is motivated by a recent discovery made by our team: Many optimization problems that are currently considered infeasible to solve (NP-hard) can be solved in low-order polynomial time if we recast the as Lex-MO problems! This includes many problems that naturally occur in practical applications.The overall aim of this proposal is to provide a detailed and systematic characterization of the class of Lex-MO optimization problems that can be solved using efficient, low-order polynomial time, algorithms. This project would lead to new algorithms, methods, and insights in combinatorial optimization with a high potential impact on many applied problems in data analysis and computer science.
Strand, Robin
Principal InvestigatorMalmberg, Filip
Coordinating organisation
Uppsala University
Funder
Period
2024-01-01 － 2027-12-31
National Category
Discrete MathematicsComputational MathematicsOther Computer and Information Science
Identifiers
DiVA, id: project:9070Project, id: 2023-03943_VR
v. 2.47.0
|
WCAG
|
Uppsala University Library
|
Ask the Library
|
Log in to DiVA
|
Search and link in DiVA