Credit points: 2
פונקציות תת-מודולריות מופיעות בתחומים רבים כגון: קומבינטוריקה, תורתהגרפים, למידת מכונה, כלכלה, ותורת האינפורמציה.בעיות אופטימיזציה בהן פונקצית המטרה היא תת-מודולרית מכלילות הן בעיותפרקטיות והן בעיות תיאורטיות קלאסיות בליבת המחקר האלגוריתמי. בקורס זהיוצג הבסיס האלגוריתמי לאופטימיזציה תת-מודולרית כאשר המיקוד יהיהבטכניקות האלגוריתמיות בהן משתמשים על מנת להתמודד עם בעיות אלה.תוצאות למידה: בסיום הקורס הסטודנטיות והסטונטים יהיו מסוגלים:1. לדעת תכונות בסיסיות של פונקציות תת-מודולריות.2. לתכנן ולנתח אלגוריתמים לבעיות אופטימיזציה תת-מודולרית.3. להשתמש בטכניקות קומבינטוריות, רנדומיות ורציפות לפתרון בעיותאוםטימיזציה תת-מודולרית.4. למדל בעיות כאופטימיזציה תת-מודולרית.
SUBMODULAR FUNCTIONS, WHICH CAPTURE THE PROPERTY OF DIMINISHINGRETURNS, ARE UBIQUITOUS IN VARIOUS DISCIPLINES, INCLUDINGCOMBINATORICS, GRAPH THEORY, MACHINE LEARNING, ECONOMICS, ALGORITHMICGAME THEORY, AND INFORMATION THEORY. THE FAMILY OF SUBMODULARMAXIMIZATION AND MINIMIZATION PROBLEMS IS A PRIME EXAMPLE OF AUNIFIED APPROACH THAT CAPTURES BOTH WELL-KNOWN CLASSIC PROBLEMS,E.G., MAX-CUT, MAX-DICUT, AND GENERALIZED ASSIGNMENT, AND REAL-WORLDAPPLICATIONS IN DIVERSE SETTINGS, E.G.,INFORMATION GATHERING, IMAGE SEGMENTATION, VIRAL MARKETING IN SOCIALNETWORKS, AND RECOMMENDATION SYSTEMS. THIS COURSE DEALS WITH THEALGORITHMIC FOUNDATIONS OF SUBMODULAR OPTIMIZATION, FOCUSING ON BASICPROBLEMS AND ALGORITHMIC TECHNIQUES. LEARNING OUTCOMES: AT THE END OFTHE COURSE THE STUDENTS WILL BE ABLE TO: 1. UNDERSTAND BASIC PROPERTIES OF SUBMODULAR FUNCTIONS.2. DESIGN AND ANALYZE ALGORITHMS FOR SUBMODULAR OPTIMIZATION.3. USE COMBINATORIAL, RANDOMIZED, AND CONTINUOUS TECHNIQUES FORSUBMODULAR OPTIMIZATION.4. MODELING OPTIMIZATION PROBLEMS AS SUBMODULAR.
פונקציות תת-מודולריות מופיעות בתחומים רבים כגון: קומבינטוריקה, תורתהגרפים, למידת מכונה, כלכלה, ותורת האינפורמציה.בעיות אופטימיזציה בהן פונקצית המטרה היא תת-מודולרית מכלילות הן בעיותפרקטיות והן בעיות תיאורטיות קלאסיות בליבת המחקר האלגוריתמי. בקורס זהיוצג הבסיס האלגוריתמי לאופטימיזציה תת-מודולרית כאשר המיקוד יהיהבטכניקות האלגוריתמיות בהן משתמשים על מנת להתמודד עם בעיות אלה.תוצאות למידה: בסיום הקורס הסטודנטיות והסטונטים יהיו מסוגלים:1. לדעת תכונות בסיסיות של פונקציות תת-מודולריות.2. לתכנן ולנתח אלגוריתמים לבעיות אופטימיזציה תת-מודולרית.3. להשתמש בטכניקות קומבינטוריות, רנדומיות ורציפות לפתרון בעיותאוםטימיזציה תת-מודולרית.4. למדל בעיות כאופטימיזציה תת-מודולרית.
SUBMODULAR FUNCTIONS, WHICH CAPTURE THE PROPERTY OF DIMINISHINGRETURNS, ARE UBIQUITOUS IN VARIOUS DISCIPLINES, INCLUDINGCOMBINATORICS, GRAPH THEORY, MACHINE LEARNING, ECONOMICS, ALGORITHMICGAME THEORY, AND INFORMATION THEORY. THE FAMILY OF SUBMODULARMAXIMIZATION AND MINIMIZATION PROBLEMS IS A PRIME EXAMPLE OF AUNIFIED APPROACH THAT CAPTURES BOTH WELL-KNOWN CLASSIC PROBLEMS,E.G., MAX-CUT, MAX-DICUT, AND GENERALIZED ASSIGNMENT, AND REAL-WORLDAPPLICATIONS IN DIVERSE SETTINGS, E.G.,INFORMATION GATHERING, IMAGE SEGMENTATION, VIRAL MARKETING IN SOCIALNETWORKS, AND RECOMMENDATION SYSTEMS. THIS COURSE DEALS WITH THEALGORITHMIC FOUNDATIONS OF SUBMODULAR OPTIMIZATION, FOCUSING ON BASICPROBLEMS AND ALGORITHMIC TECHNIQUES. LEARNING OUTCOMES: AT THE END OFTHE COURSE THE STUDENTS WILL BE ABLE TO: 1. UNDERSTAND BASIC PROPERTIES OF SUBMODULAR FUNCTIONS.2. DESIGN AND ANALYZE ALGORITHMS FOR SUBMODULAR OPTIMIZATION.3. USE COMBINATORIAL, RANDOMIZED, AND CONTINUOUS TECHNIQUES FORSUBMODULAR OPTIMIZATION.4. MODELING OPTIMIZATION PROBLEMS AS SUBMODULAR.